A - Anyway Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c, d が与えられるので、以下の指示に従って 2 行出力してください。

1 行目は (a + b) \times (c - d) の計算結果を整数として出力してください。
2 行目は入力にかかわらず Takahashi と出力してください。

制約

  • -100 \leq a, b, c, d \leq 100
  • a,b,c,d は整数

入力

入力は以下の形式で標準入力から与えられる。

a b c d 

出力

問題文の指示に従って 2 行出力せよ。


入力例 1

1 2 5 3

出力例 1

6
Takahashi

(1 + 2) \times(5 - 3) = 3 \times 2 = 6 です。よって 1 行目は 6 を出力します。
2 行目は Takahashi を出力します。1 文字目を小文字にしたりスペルを誤ったりすると誤答となるので注意してください。


入力例 2

10 -20 30 -40

出力例 2

-700
Takahashi

入出力に負の数が含まれる場合もあります。


入力例 3

100 100 100 -100

出力例 3

40000
Takahashi

Score : 100 points

Problem Statement

You are given integers a, b, c, and d. Print two lines as follows.

The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.

Constraints

  • -100 \leq a, b, c, d \leq 100
  • a, b, c, and d are integers.

Input

The input is given from Standard Input in the following format:

a b c d 

Output

Print two lines according to the Problem Statement.


Sample Input 1

1 2 5 3

Sample Output 1

6
Takahashi

We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.


Sample Input 2

10 -20 30 -40

Sample Output 2

-700
Takahashi

The input or output may contain negative numbers.


Sample Input 3

100 100 100 -100

Sample Output 3

40000
Takahashi
B - First Grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

縦 2 行、横 2 列のグリッド(各マスが正方形のマス目)があります。
このグリッドは、各マスが黒か白であり、少なくとも 2 つの黒マスを含みます。
各マスの色の情報は文字列 S_1,S_2 として、以下の形式で与えられます。

  • 文字列 S_i の j 文字目が # であれば上から i マス目、左から j マス目は黒
  • 文字列 S_i の j 文字目が . であれば上から i マス目、左から j マス目は白

2 つの異なる黒マス同士が辺で接している時、またその時に限りそれら 2 つの黒マスは直接行き来できます。
黒マスのみをいくつか通ることによって、どの 2 つの黒マス同士も(直接または間接的に)行き来できるかどうか判定してください。

制約

  • S_1,S_2 は # または . からなる 2 文字の文字列
  • S_1,S_2 に # が合計で 2 つ以上含まれる

入力

入力は以下の形式で標準入力から与えられる。

S_1
S_2

出力

どの 2 つの黒マス同士も行き来できるなら Yes 、そうでないなら No と出力せよ。


入力例 1

##
.#

出力例 1

Yes

左上の黒マスと右上の黒マス、右上の黒マスと右下の黒マスを直接行き来することができます。
これらの移動を用いてどの黒マスからどの黒マスへも行き来できるので、答えは Yes となります。


入力例 2

.#
#.

出力例 2

No

右上の黒マスと左下の黒マスを行き来することはできません。答えは No となります。

Score : 100 points

Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

  • If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
  • If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

  • Each of S_1 and S_2 is a string with two characters consisting of # and ..
  • S_1 and S_2 have two or more #s in total.

Input

Input is given from Standard Input in the following format:

S_1
S_2

Output

If it is possible to travel from every black square to every black square, print Yes; otherwise, print No.


Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.


Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

C - Cat

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

  • N は 1 以上 1000 以下の整数
  • S は英小文字からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。


入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。


入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。


入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

  • N is an integer between 1 and 1000, inclusive.
  • S is a string of length N consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.


Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.


Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.


Sample Input 3

8
national

Sample Output 3

nyationyal
D - typo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。

  • S の隣り合う 2 文字を選び、入れ替える。

なお、上記の操作を一度も行わないことも可能です。

制約

  • S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
  • S の長さと T の長さは等しい

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。


入力例 1

abc
acb

出力例 1

Yes

S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。


入力例 2

aabb
bbaa

出力例 2

No

どのように操作を行っても、S を T と一致させることはできません。


入力例 3

abcde
abcde

出力例 3

Yes

S と T は既に一致しています。

Score : 200 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

  • choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

  • Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
  • S and T have the same length.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.


Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.


Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.


Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

E - Collision 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

xy 座標平面上に N 人の人がいます。人 i は (X_i, Y_i) にいます。すべての人は異なる地点にいます。

L, R からなる長さ N の文字列 S があります。
人 i は S_i = R ならば右向きに、S_i = L ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。

たとえば (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL の場合は次の図のように動きます。

image

反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか?

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9
  • 0 \leq Y_i \leq 10^9
  • i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j) である。
  • X_i, Y_i はすべて整数である。
  • S は L および R からなる長さ N の文字列である。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

出力

衝突が発生するならば Yes を、発生しないならば No を出力せよ。


入力例 1

3
2 3
1 1
4 1
RRL

出力例 1

Yes

この入力は問題文にある例と同じケースです。
すべての人が歩き続けると人 2 と人 3 が衝突します。よって Yes を出力します。


入力例 2

2
1 1
2 1
RR

出力例 2

No

人 1 と人 2 は同じ向きに歩いているので衝突することはありません。


入力例 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

出力例 3

Yes

Score : 300 points

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

image

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq X_i \leq 10^9
  • 0 \leq Y_i \leq 10^9
  • (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
  • All X_i and Y_i are integers.
  • S is a string of length N consisting of L and R.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

Output

If there will be a collision, print Yes; otherwise, print No.


Sample Input 1

3
2 3
1 1
4 1
RRL

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.


Sample Input 2

2
1 1
2 1
RR

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.


Sample Input 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Sample Output 3

Yes
F - ±1 Operation 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 X が与えられます。この X に以下を施すことを「操作」と呼びます。

  • 以下の 2 つのうちどちらかを選択し、実行する。
    • X に 1 を加算する。
    • X から 1 を減算する。

初項 A 、公差 D 、項数 N の等差数列 S に含まれる数を「良い数」と呼びます。
「操作」を 0 回以上何度でも使って X を「良い数」にする時、必要な「操作」の最小回数を求めてください。

制約

  • 入力は全て整数
  • -10^{18} \le X,A \le 10^{18}
  • -10^6 \le D \le 10^6
  • 1 \le N \le 10^{12}

入力

入力は以下の形式で標準入力から与えられる。

X A D N

出力

答えを整数として出力せよ。


入力例 1

6 2 3 3

出力例 1

1

A=2,D=3,N=3 であるため、 S=(2,5,8) です。
X=6 を「良い数」にするためには、 X から 1 を減算することを 1 度行えば良いです。
0 回の操作で X を「良い数」にすることはできません。


入力例 2

0 0 0 1

出力例 2

0

D=0 である場合もあります。また、操作を 1 回も必要としない場合もあります。


入力例 3

998244353 -10 -20 30

出力例 3

998244363

入力例 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

出力例 4

444445

Score : 300 points

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

  • Choose and do one of the following.
    • Add 1 to X.
    • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

  • All values in input are integers.
  • -10^{18} \le X,A \le 10^{18}
  • -10^6 \le D \le 10^6
  • 1 \le N \le 10^{12}

Input

Input is given from Standard Input in the following format:

X A D N

Output

Print the answer as an integer.


Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.


Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.


Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445
G - Happy New Year 2023

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

正整数 N が与えられます。N は、2 つの相異なる素数 p,q を用いて N=p^2q と表せることがわかっています。

p,q を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 入力は全て整数
  • 1\leq T\leq 10
  • 1\leq N \leq 9\times 10^{18}
  • N は、2 つの相異なる素数 p,q を用いて N=p^2q と表せる

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

各テストケースは以下の形式で与えられる。

N

出力

T 行出力せよ。

i\ (1\leq i \leq T) 行目には、i 番目のテストケースにおける p,q を空白区切りで出力せよ。 なお、この問題の制約下では、N=p^2q を満たす素数 p,q の組は 1 通りしか存在しないことが証明できる。


入力例 1

3
2023
63
1059872604593911

出力例 1

17 7
3 7
104149 97711

1 番目のテストケースについて、N=2023=17^2\times 7 です。よって、p=17,q=7 です。

Score : 400 points

Problem Statement

You are given a positive integer N. It is known that N can be represented as N=p^2q using two different prime numbers p and q.

Find p and q.

You have T test cases to solve.

Constraints

  • All values in the input are integers.
  • 1\leq T\leq 10
  • 1\leq N \leq 9\times 10^{18}
  • N can be represented as N=p^2q using two different prime numbers p and q.

Input

The input is given from Standard Input in the following format, where \text{test}_i represents the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is in the following format:

N

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain p and q for the i-th test case, separated by a space. Under the constraints of this problem, it can be proved that the pair of prime numbers p and q such that N=p^2q is unique.


Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have N=2023=17^2\times 7. Thus, p=17 and q=7.

H - Distinct Adjacent

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

1 から N の番号がついた N 人の人が輪になってならんでいます。人 1 の右隣には人 2 が、人 2 の右隣には人 3 が、……、人 N の右隣には人 1 がいます。

N 人の人にそれぞれ 0 以上 M 未満の整数を 1 つずつ渡します。
M^N 通りの渡し方のうち、どの隣り合う 2 人が渡された数も異なるものの数を、998244353 で割ったあまりを求めてください。

制約

  • 2 \leq N,M \leq 10^6
  • N,M は整数である

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

答えを出力せよ。


入力例 1

3 3

出力例 1

6

人 1,2,3 に渡す整数がそれぞれ (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0) のときの 6 通りです。


入力例 2

4 2

出力例 2

2

人 1,2,3,4 に渡す整数がそれぞれ (0,1,0,1),(1,0,1,0) のときの 2 通りです。


入力例 3

987654 456789

出力例 3

778634319

998244353 で割ったあまりを求めてください。

Score : 475 points

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

  • 2 \leq N,M \leq 10^6
  • N and M are integers.

Input

The input is given from Standard Input in the following format:

N M

Output

Print the answer.


Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).


Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).


Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

I - Two Spanning Trees

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の無向グラフ G が与えられます。 G は単純(自己ループおよび多重辺を持たない)かつ連結です。

i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結ぶ無向辺 \lbrace u_i, v_i \rbrace です。

下記の 2 つの条件をともに満たすような G の 2 つの全域木 T_1,T_2 を 1 組構成してください。( T_1 と T_2 は異なる全域木である必要はありません。)

  • T_1 は下記を満たす。

    T_1 を頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T_1 に含まれないすべての辺 \lbrace u, v \rbrace について、u と v は T_1 において祖先と子孫の関係にある。

  • T_2 は下記を満たす。

    T_2 を頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T_2 に含まれない辺 \lbrace u, v \rbrace であって、u と v が T_2 において祖先と子孫の関係にあるようなものは存在しない。

ここで、「根付き木 T において頂点 u と頂点 v が祖先と子孫の関係にある」とは、「 T において u が v の祖先である」と「 T において v が u の祖先である」のうちどちらかが成り立つことをいいます。

本問題の制約下において上記の条件を満たす T_1 と T_2 は必ず存在することが示せます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • 入力はすべて整数
  • 与えられるグラフは単純かつ連結

入力

入力は以下の形式で標準入力から与えられます。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

T_1 と T_2 を下記の形式にしたがって、2N-2 行にわたって出力してください。すなわち、

  • 1 行目から N-1 行目には、T_1 に含まれる N-1 本の無向辺 \lbrace x_1, y_1\rbrace, \lbrace x_2, y_2\rbrace, \ldots, \lbrace x_{N-1}, y_{N-1}\rbrace を、各行に 1 本ずつ出力してください。
  • N 行目から 2N-2 行目には、T_2 に含まれる N-1 本の無向辺 \lbrace z_1, w_1\rbrace, \lbrace z_2, w_2\rbrace, \ldots, \lbrace z_{N-1}, w_{N-1}\rbrace を、各行に 1 本ずつ出力してください。

各全域木を構成する辺をどのような順番で出力するかや、各辺の出力においてどちらの端点を先に出力するかは任意です。

x_1 y_1
x_2 y_2
\vdots
x_{N-1} y_{N-1}
z_1 w_1
z_2 w_2
\vdots
z_{N-1} w_{N-1}

入力例 1

6 8
5 1
4 3
1 4
3 5
1 2
2 6
1 6
4 2

出力例 1

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

上記の出力例において、T_1 は 5 本の辺 \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace を持つ G の全域木です。この T_1 は問題文中の条件を満たします。実際、G の辺のうち T_1 に含まれない各辺に関して、

  • 辺 \lbrace 5, 1 \rbrace について、頂点 1 は頂点 5 の祖先であり、
  • 辺 \lbrace 1, 2 \rbrace について、頂点 1 は頂点 2 の祖先であり、
  • 辺 \lbrace 1, 6 \rbrace について、頂点 1 は頂点 6 の祖先です。

また、T_2 は 5 本の辺 \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace を持つ G の全域木です。この T_2 は問題文中の条件を満たします。実際、G の辺のうち T_2 に含まれない各辺に関して、

  • 辺 \lbrace 4, 3 \rbrace について、頂点 4 と頂点 3 は祖先と子孫の関係になく、
  • 辺 \lbrace 2, 6 \rbrace について、頂点 2 と頂点 6 は祖先と子孫の関係になく、
  • 辺 \lbrace 4, 2 \rbrace について、頂点 4 と頂点 2 は祖先と子孫の関係にありません。

入力例 2

4 3
3 1
1 2
1 4

出力例 2

1 2
1 3
1 4
1 4
1 3
1 2

3 本の辺 \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace を持つ木 T が G の唯一の全域木です。 G の辺のうちこの木 T に含まれない辺は存在しないので、明らかに、T は T_1 の条件と T_2 の条件をともに満たします。

Score : 500 points

Problem Statement

You are given an undirected graph G with N vertices and M edges. G is simple (it has no self-loops and multiple edges) and connected.

For i = 1, 2, \ldots, M, the i-th edge is an undirected edge \lbrace u_i, v_i \rbrace connecting Vertices u_i and v_i.

Construct two spanning trees T_1 and T_2 of G that satisfy both of the two conditions below. (T_1 and T_2 do not necessarily have to be different spanning trees.)

  • T_1 satisfies the following.

    If we regard T_1 as a rooted tree rooted at Vertex 1, for any edge \lbrace u, v \rbrace of G not contained in T_1, one of u and v is an ancestor of the other in T_1.

  • T_2 satisfies the following.

    If we regard T_2 as a rooted tree rooted at Vertex 1, there is no edge \lbrace u, v \rbrace of G not contained in T_2 such that one of u and v is an ancestor of the other in T_2.

We can show that there always exists T_1 and T_2 that satisfy the conditions above.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • All values in input are integers.
  • The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print (2N-2) lines to output T_1 and T_2 in the following format. Specifically,

  • The 1-st through (N-1)-th lines should contain the (N-1) undirected edges \lbrace x_1, y_1\rbrace, \lbrace x_2, y_2\rbrace, \ldots, \lbrace x_{N-1}, y_{N-1}\rbrace contained in T_1, one edge in each line.
  • The N-th through (2N-2)-th lines should contain the (N-1) undirected edges \lbrace z_1, w_1\rbrace, \lbrace z_2, w_2\rbrace, \ldots, \lbrace z_{N-1}, w_{N-1}\rbrace contained in T_2, one edge in each line.

You may print edges in each spanning tree in any order. Also, you may print the endpoints of each edge in any order.

x_1 y_1
x_2 y_2
\vdots
x_{N-1} y_{N-1}
z_1 w_1
z_2 w_2
\vdots
z_{N-1} w_{N-1}

Sample Input 1

6 8
5 1
4 3
1 4
3 5
1 2
2 6
1 6
4 2

Sample Output 1

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

In the Sample Output above, T_1 is a spanning tree of G containing 5 edges \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace. This T_1 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_1:

  • for edge \lbrace 5, 1 \rbrace, Vertex 1 is an ancestor of 5;
  • for edge \lbrace 1, 2 \rbrace, Vertex 1 is an ancestor of 2;
  • for edge \lbrace 1, 6 \rbrace, Vertex 1 is an ancestor of 6.

T_2 is another spanning tree of G containing 5 edges \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace. This T_2 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_2:

  • for edge \lbrace 4, 3 \rbrace, Vertex 4 is not an ancestor of Vertex 3, and vice versa;
  • for edge \lbrace 2, 6 \rbrace, Vertex 2 is not an ancestor of Vertex 6, and vice versa;
  • for edge \lbrace 4, 2 \rbrace, Vertex 4 is not an ancestor of Vertex 2, and vice versa.

Sample Input 2

4 3
3 1
1 2
1 4

Sample Output 2

1 2
1 3
1 4
1 4
1 3
1 2

Tree T, containing 3 edges \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, is the only spanning tree of G. Since there are no edges of G that are not contained in T, obviously this T satisfies the conditions for both T_1 and T_2.