A. EhAb AnD gCd

You are given a positive integer $x$ . Find any such $2$ positive integers $a$ and $b$ such that $GCD(a,b)+LCM(a,b)=x$ .
As a reminder, $GCD(a,b)$ is the greatest integer that divides both $a$ and $b$ . Similarly, $LCM(a,b)$ is the smallest integer such that both $a$ and $b$ divide it.
It’s guaranteed that the solution always exists. If there are several such pairs $(a,b)$ , you can output any of them.

Input

The first line contains a single integer $t (1≤t≤100)$ — the number of testcases.
Each testcase consists of one line containing a single integer, $x (2≤x≤10^9)$ .

Output

For each testcase, output a pair of positive integers $a$ and $b$ $(1≤a,b≤10^9)$ such that $GCD(a,b)+LCM(a,b)=x$ . It’s guaranteed that the solution always exists. If there are several such pairs $(a,b)$ , you can output any of them.

Example

input

2
2
14

output

1 1
6 4

Note

In the first testcase of the sample, $GCD(1,1)+LCM(1,1)=1+1=2$ .
In the second testcase of the sample, $GCD(6,4)+LCM(6,4)=2+12=14$ .

Translation

给一个数 $x$ ，任意输出一个数对 $(a,b)$ ，满足 $GCD(a,b)+LCM(a,b)=x$ 。

Idea

如官方题解所说：“ $1$ and $n-1$ always work.”

Code

#include<iostream>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	cout<<1<<' '<<n-1<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

Postscript

有时候只需要灵机一动。

B. CopyCopyCopyCopyCopy

Ehab has an array $a$ of length $n$ . He has just enough free time to make a new array consisting of $n$ copies of the old array, written back-to-back. What will be the length of the new array’s longest increasing subsequence?
A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.

Input

The first line contains an integer $t$ — the number of test cases you need to solve. The description of the test cases follows.
The first line of each test case contains an integer $n$ $(1≤n≤10^5)$ — the number of elements in the array $a$ .
The second line contains n space-separated integers $a_1, a_2,\dots, a_n$ $ (1≤a_i≤10^9)$ — the elements of the array $a$ .
The sum of $n$ across the test cases doesn’t exceed $10^5$ .

Output

For each testcase, output the length of the longest increasing subsequence of a if you concatenate it to itself $n$ times.

Example

input

2
3
3 2 1
6
3 1 4 1 5 9

output

3
5

Note

In the first sample, the new array is $[3,2,1,3,2,1,3,2,1]$ . The longest increasing subsequence is marked in bold.
In the second sample, the longest increasing subsequence will be $[1,3,4,5,9]$ .

Translation

给一个数列 $\{a_n\}$ ，将该数列复制 $n-1$ 次，依次拼接到 $\{a_n\}$ 的尾部。得到新数列 $\{a_{n\times n}\}$ ，问 $\{a_{n\times n}\}$ 最长严格上升子序列的长度。

Idea

观察样例，能够猜到答案就是数列 $\{a_n\}$ 中数字的种类数 $d$ 。
下面给出证明：
将这 $d$ 个不重复的数字从大到小排序，我们可以从原数列中拿出第一个，从第一个复制数列中拿出第二个……从第 $d-1$ 个复制数列中拿出第 $d$ 个。由于 $d\leqslant n$ 恒成立，必能找到一个长度为 $d$ 的严格上升子序列。假设存在比 $d$ 更长的严格上升子序列，那么原数列中数字的种类数大于 $d$ ，矛盾。所以答案就是原数列中数字的种类数，证毕。
代码实现就是用 $STL$ 中的 $set$ 存一下。

Code

#include<iostream>
#include<set>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	set<int>ex;
	int i;
	for(i=1;i<=n;i++)
	{
		int temp;
		cin>>temp;
		ex.insert(temp);
	}
	cout<<ex.size()<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

Postscript

大胆假设，小心求证。

C. Ehab and Path-etic MEXs

You are given a tree consisting of $n$ nodes. You want to write some labels on the tree’s edges such that the following conditions hold:

Every label is an integer between $0$ and $n−2$ inclusive.
All the written labels are distinct.
The largest value among $MEX(u,v)$ over all pairs of nodes $(u,v)$ is as small as possible.

Here, $MEX(u,v)$ denotes the smallest non-negative integer that isn’t written on any edge on the unique simple path from node $u$ to node $v$ .

Input

The first line contains the integer $n$ $(2≤n≤10^5)$ — the number of nodes in the tree.
Each of the next $n−1$ lines contains two space-separated integers $u$ and $v$ $(1≤u,v≤n)$ that mean there’s an edge between nodes $u$ and $v$ . It’s guaranteed that the given graph is a tree.

Output

Output $n−1$ integers. The $i^{th}$ of them will be the number written on the $i^{th}$ edge (in the input order).

Examples

input

3
1 2
1 3

output

0
1

input

6
1 2
1 3
2 4
2 5
5 6

output

0
3
2
4
1

Note

The tree from the second sample:

Translation

给一棵 $n$ 个顶点的树，将树的边从 $0$ 到 $n-2$ 编号，使得任意两点 $(u,v)$ 的 $MEX(u,v)$ 最大值尽可能小。
$MEX(u,v)$ 指 $(u,v)$ 之间的简单路径上不存在的最小非负边权。

Idea

先来理解一下 $MEX(u,v)$ 。样例中 $MEX(1,5)=1,MEX(1,4)=0,MEX(1,6)=2$ 。
可以观察到，如果这棵树是一条链，那么无论怎么排，整条链的 $MEX$ 都为 $n-1$ ；对于一颗正常的树，无论怎样给边赋值，总会有一条简单路径存在两条边权为 $0$ 和 $1$ 的边；因此，我们的目标是使 $MEX(u,v)(u,v\in [1,n])$ 的最大值为 $2$ 。
对于一棵正常树，如果存在某一个节点度数大于等于 $3$ ，选择其中三条边编号 $0,1,2$ 。这样其他的路径一定不会同时经过 $0,1,2$ 。而无论怎么排列，一定无法避免其中会有一条路径同时经过 $0,1$ 。所以所有路径的 $MEX$ 的最大值一定为 $2$ ；剩余的边随便排就可以了。

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int N=200005;
vector<int>G[N];//存图
map<pair<int,int>,int>id;//记录每一条边的编号
int ans[N];//存答案
void solve()
{
	int n;
	cin>>n;
	memset(ans,-1,sizeof(ans));//初始化
	int i;
	for(i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		id[make_pair(u,v)]=i;//设置编号
	}
	int start=0;
	for(i=1;i<=n;i++)
	{
		if(G[i].size()>=3)//找到度数大于等于3的点
		{
			int j;
			for(j=0;j<G[i].size();j++)
			{
				//赋值0,1,2,多出来的点随意赋值
				if(id.find(make_pair(i,G[i][j]))==id.end())
				{
					ans[id[make_pair(G[i][j],i)]]=j;
				}
				else ans[id[make_pair(i,G[i][j])]]=j;
			}
			start=G[i].size();//记录剩余的可使用数字
			break;
		}
	}
	for(i=1;i<=n-1;i++)
	{
		if(ans[i]==-1)//还未更新则赋值
		{
			ans[i]=start;
			start++;
		}
	}
	//输出  
	for(i=1;i<=n-1;i++) cout<<ans[i]<<endl;
}
int main()
{
	solve();
	return 0;
}

Postscript

思维题，多想，多看，多写，多画。

D. Ehab the Xorcist

Given $2$ integers $u$ and $v$ , find the shortest array such that bitwise-xor of its elements is $u$ , and the sum of its elements is $v$ .

Input

The only line contains $2$ integers $u$ and $v$ $(0≤u,v≤10^{18})$ .

Output

If there’s no array that satisfies the condition, print “-1”. Otherwise:
The first line should contain one integer, $n$ , representing the length of the desired array. The next line should contain $n$ positive integers, the array itself. If there are multiple possible answers, print any.

Examples

input

2 4

output

2
3 1

input

1 3

output

3
1 1 1

input

8 5

output

-1

input

0 0

output

Note

In the first sample, $3⊕1=2$ and $3+1=4$ . There is no valid array of smaller length.
Notice that in the fourth sample the array is empty.

Translation

给两个整数 $u,v$ ，找到一个最短的非负整数数列，使得数列的异或和为 $u$ ，加法和为 $v$ 。
将 $v$ 拆分， $v=u+\frac {v-u}{2}+ \frac {v-u}{2}$ 。可以看到，当 $u>v$ ，无解；当 $u,v$ 奇偶性不同，无解。如果有解，当 $u=v$ ，时，我们需要特判一下；当 $u\ne v$ ，一定可以找到一个含三个元素的数列 $\left[u,\frac {v-u}{2},\frac {v-u}{2}\right]$ ，若满足 $u\oplus \left (\frac{v-u}{2} \right)=u+\frac{v-u}{2}$ ，则 $\left[u\oplus \left (\frac{v-u}{2} \right)\right]\oplus\left(\frac{v-u}{2}\right)=\left(u+\frac{v-u}{2}\right)\oplus\left(\frac{v-u}{2}\right)$ ，则构造出了两个元素的数列 $\left[\frac{v+u}{2},\frac{v-u}{2}\right]$ 。

Code

#include<iostream>
using namespace std;
void solve()
{
	long long u,v;
	cin>>u>>v;
	if(u>v) cout<<-1;
	else if((u+v)&1) cout<<-1;
	else
	{
		if(u==v)
		{
			if(!u) cout<<0;
			else cout<<1<<endl<<u; 
		}
		else
		{
			//可合并（加法和异或的效果相同） 
			if((u^(v-u>>1))==(v-u>>1)+u) cout<<2<<endl<<(v+u>>1)<<' '<<(v-u>>1);
			//不可合并 
			else cout<<3<<endl<<u<<' '<<(v-u>>1)<<' '<<(v-u>>1);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}