Để xây dựng cấu trúc dữ liệu disjoint sets union, bạn cần phải thực hiện ~2~ loại truy vấn sau:

• union ~u~ ~v~ — gộp hai tập hợp lần lượt chứa ~u~ và ~v~.

• get ~u~ ~v~ — kiểm tra ~u~ và ~v~ có thuộc cùng một tập hợp hay không.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~1 \le n,m \le 10^5~) — lần lượt là số lượng phần tử và số lượng truy vấn. ~m~ dòng tiếp theo là các truy vấn, mỗi truy vấn ghi trên một dòng.

• Truy vấn union có dạng: union ~u~ ~v~ (~1 \le u,v \le n~).

• Truy vấn get có dạng: get ~u~ ~v~ (~1 \le u, v \le n~).

Output

In ra kết quả của mỗi truy vấn get trên một dòng theo thứ tự: "YES", nếu các phần tử thuộc cùng một tập hợp, và ngược lại in ra "NO".

Scoring

Sample Input 1

4 4
union 1 2
union 1 3
get 1 4
get 2 3

Sample Output 1

NO
YES

Cho một đồ thị gồm ~n~ đỉnh, ban đầu đồ thị không có cạnh nào. Trong đó, đỉnh thứ ~i~ có giá trị là ~i~.

Cho ~m~ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• union ~u~ ~v~ (~1 \leq u, v \leq n~) — Nối một cạnh giữa hai đỉnh ~u~ và ~v~.

• get ~u~ (~1 \leq u \leq n~) — Trong thành phần chứa đỉnh ~u~, tìm giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \leq n, m \leq 3 \times 10^5~) — Là số đỉnh của đồ thị và số truy vấn.

Trong ~m~ dòng tiếp theo, mỗi dòng là một loại truy vấn thuộc một trong hai loại trên.

Output

Với mỗi thao tác loại get, hãy in ra 3 số nguyên dương trên từng dòng. Thứ tự in của 3 số nguyên dương trên mỗi dòng lần lượt là: giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Scoring

Sample Input 1

5 11
union 1 2
get 3
get 2
union 2 3
get 2
union 1 3
get 5
union 4 5
get 5
union 4 1
get 5

Sample Output 1

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

Farmer John và em đang chăn bò ở trên trang trại của mình. Vì thấy chán nên Farmer John đã ra một trò chơi cho người em.

Hiện tại, trên trang có ~N~ cái chuồng đang trống và độc lập nhau. Vì là quản trò nên Farmer John sẽ ra ~K~ lượt ra hiệu lệnh và có ba loại hiệu lệnh sau:

• join ~X~ ~Y~: kết nối chuồng thứ ~X~ và chuồng thứ ~Y~ lại với nhau.

• add ~X~ ~V~: cho chuồng thứ ~X~ và những chuồng được kết nối với chuồng ~X~ thêm ~V~ ~(V\le100)~ con bò. Hai chuồng ~X~ và ~Y~ kết nối với nhau nếu như từ chuồng ~X~ ta có thể đi đến chuồng ~Y~ qua một số chuồng trung gian được kết nối với nhau.

• get ~X~: Farmer John hỏi em rằng chuồng thứ ~X~ có bao nhiêu con bò

Vì em của Farmer John còn non trẻ nên đã nhò bạn làm bài này. Bạn hãy giúp đỡ nhé.

Input

• Dòng đầu tiền gồm hai số ~N~ và ~K~ ~(N\le10^5,K\le5\times10^5)~.

• ~K~ dòng tiếp theo là lệnh của Farmer John.

Output

Gồm một số dòng là kết quả của các lệnh get, mỗi lệnh trên một dòng.

Scoring

Sample Input 1

4 10
join 1 2
add 1 100
join 2 3
add 1 50
join 3 4
add 1 25
get 1
get 2
get 3
get 4

Sample Output 1

175
175
75
25

Có ~n~ con khỉ đang treo mình trên ~1~ cái cây rất cao. Những con khỉ được đánh số từ ~1~ đến ~n~. Con khỉ đầu đàn được đánh số là ~1~ và hiện tại nó đang treo mình trên cây bằng cách sử dụng đuôi của nó. ~1~ con khỉ có ~2~ tay và nó có thể dùng mỗi tay để bám vào đuôi của ~1~ con khỉ (có thể tự bám vào đuôi của chính nó). Mỗi tay chỉ có thể bám được nhiều nhất ~1~ đuôi nhưng mỗi cái đuôi có thể được bám bởi nhiều tay khác nhau. Trong ~m~ giây sắp tới (từ giây thứ ~0~ đến giây thứ ~m-1~) mỗi giây sẽ có ~1~ con khỉ buông ~1~ tay của nó. Việc của bạn là với mỗi con khỉ hãy tính thời điểm mà nó bị rơi khỏi cây.

Input

Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n \le 2\cdot10^5, 1 \le m \le 4\cdot10^5)~ với ~n~ là số con khỉ và ~m~ là số giây mà ta sẽ quan tâm.

~n~ dòng tiếp theo chứa ~2~ số nguyên dương ~l_i, r_i~. ~l_i~ sẽ có giá trị là ~-1~ hoặc chỉ số của con khỉ mà tay trái của con khỉ thứ ~i~ đang nắm đuôi. Tương tự với ~r_i~ sẽ có giá trị là ~-1~ hoặc chỉ số của con khỉ mà tay phải của con khỉ thứ ~i~ đang nắm đuôi. Giá trị ~-1~ tức là tay của con khỉ thứ ~i~ hiện đang không nắm đuôi con khỉ nào. Con khỉ đầu đàn (con khỉ mang số thứ tự ~1~) thì dùng đuôi của nó để bám vào cành cây.

~m~ dòng tiếp theo mô tả sự kiện sẽ diễn ra trong ~m~ giây từ ~0~ đến ~m-1~. Dòng thứ ~j~ sẽ gồm ~2~ chỉ số ~p_j~ và ~h_j~ ám chỉ việc ~1~ con khỉ sẽ buông tay. ~p_j~ là chỉ số của con khỉ buông tay ~(1 \le p_j \le n)~ và ~h_j~ sẽ mang giá trị ~1~ nếu con khỉ ~p_j~ buông tay trái hoặc mang giá trị ~2~ nếu con khỉ ~p_j~ buông tay phải.

Dữ liệu luôn đảm bảo con khỉ sẽ không buông tay nếu tại thời điểm truy vấn nó không nắm cái đuôi nào. Các con khỉ có thể dùng cả ~2~ tay để nằm đuổi của cùng ~1~ con khỉ và cũng có thể dùng tay để tự nắm đuôi của chính nó.

Output

In ra ~n~ dòng. Dòng thứ ~i~ là thời điểm mà con khỉ thứ ~i~ bắt đầu rơi từ trên cây xuống. Nếu con khỉ không bao giờ rơi xuống thì in ra ~-1~.

Scoring

Sample Input 1

3 2
-1 3
3 -1
1 2
1 2
3 1

Sample Output 1

-1
1
1

Sample Input 2

4 5
2 2
3 -1
4 -1
-1 2
1 1
2 1
3 1
1 2
4 2

Sample Output 2

-1
3
2
3

Cho một đồ thị vô hướng và một dãy các truy vấn thuộc một trong hai loại sau:

• cut ~u~ ~v~ — xóa cạnh ~u-v~ khỏi đồ thị;

• ask ~u~ ~v~ — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không.

Sau khi thực hiện tất cả truy vấn, đồ thị không còn cạnh nào. Tìm đáp án cho mỗi truy vấn thuộc loại ask.

Input

Dòng đầu tiên gồm ba số nguyên dương ~n, m~ và ~k~ (~1 \le n \le 50000, 0 \le m \le 100000, m \le k \le 150000~) — lần lượt là số lượng đỉnh, số lượng cạnh trong đồ thị và số lượng truy vấn cần thực hiện.

Mỗi dòng trong ~m~ dòng tiếp theo gồm hai số nguyên dương ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~) — hai đỉnh của cạnh thứ ~i~. Các đỉnh được đánh số từ ~1~, đồ thị không có khuyên và cạnh lặp.

Mỗi dòng trong ~k~ dòng tiếp theo mô tả một trong hai loại truy vấn sau:

• "cut ~u~ ~v~" — xóa cạnh giữa đỉnh ~u~ và ~v~

• "ask ~u~ ~v~" — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không

Mỗi cạnh trong đồ thị xuất hiện trong các truy vấn cut một lần.

Output

Với mỗi truy vấn thuộc loại ask, in ra "YES" nếu hai đỉnh đã cho cùng thuộc một thành phần liên thông, và "NO" trong trường hợp còn lại. Thứ tự in ra đáp án tương đương với thứ tự truy vấn ask xuất hiện.

Scoring

Sample Input 1

3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1

Sample Output 1

YES
YES
NO
NO

~n~ người đang đứng ở các vị trí từ ~1~ đến ~n~. Bạn cần thực hiện các truy vấn thuộc hai loại sau:

• "- x" — người ở vị trí ~x~ rời đi;

• "? x" — tìm người gần nhất đứng bên phải vẫn còn đứng.

Input

Dòng đầu tiên của đầu vào chứa hai số nguyên ~n~ và ~m~ (~1 \leq n, m \leq 10^6~) — số người và số truy vấn.

Tiếp theo là ~m~ dòng chứa các truy vấn, mỗi dòng một truy vấn. Với các truy vấn về việc rời đi, dòng truy vấn có dạng "- x" (~1 \leq x \leq n~). Với các truy vấn về người gần nhất, dòng truy vấn có dạng "? x" (~1 \leq x \leq n~).

Dữ liệu đảm bảo rằng tất cả những người rời đi đều khác nhau.

Output

In ra kết quả của mỗi thao tác "?" theo từng dòng theo thứ tự tương ứng. Nếu không có người nào bên phải — in ra "-1".

Scoring

Sample Input 1

5 10
? 1
- 3
? 3
- 2
? 1
? 2
- 4
? 3
- 5
? 3

Sample Output 1

1
4
1
4
5
-1

Có ~n~ ô đỗ xe tạo thành hình vòng cung được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Có ~n~ chiếc xe đến đỗ xe, xe nào đến trước thì được ưu tiên đỗ trước. Tại thời điểm ~i~, xe thứ ~i~ đến ô thứ ~p_i~ và muốn đỗ xe ở đó, nếu tại ô thứ ~p_i~ đã có xe đỗ trước đó thì xe thứ ~i~ sẽ đi theo chiều kim đồng hồ cho đến khi gặp được ô đỗ xe đầu tiên không có xe và thực hiện đỗ xe ở đó.

Input

Dòng đầu tiên là số nguyên dương ~n~ — số lượng ô đỗ xe và số xe đến đỗ (~1 \le n \le 3 \cdot 10^5~).

Dòng thứ hai gồm ~n~ số nguyên dương ~p_i~ — ô đỗ xe mà xe thứ ~i~ muốn đỗ (~1 \le p_i \le n~).

Output

In ra ~n~ số nguyên dương, số thứ ~i~ là số hiệu của ô đỗ xe mà xe thứ ~i~ sẽ đỗ.

Scoring

Sample Input 1

3
2 2 2

Sample Output 1

2 3 1

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
4 5 3 2 1 1 5 8 9 10

Sample Output 3

4 5 3 2 1 6 7 8 9 10

Sample Input 4

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sample Output 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Notes

Giải thích test ví dụ: Xe ~1~ là xe đến đầu tiên và được đỗ tại ô ~2~. Sau đó xe ~2~ đến, do ô ~2~ đã được xe ~1~ đỗ nên xe ~2~ đi theo chiều kim đồng hồ và đỗ vào ô đầu tiên chưa có xe đỗ là ô ~3~. Cuối cùng, xe ~3~ đến và phải đỗ vào ô ~1~ do cả ô ~2~ và ô ~3~ đã có xe đỗ.

Ngay cả công ty thành công nhất cũng có thể trải qua giai đoạn khủng hoảng khi bạn phải đưa ra quyết định khó khăn — tái cấu trúc, loại bỏ và sáp nhập các phòng ban, sa thải nhân viên và làm những việc khó chịu khác. Hãy cùng xem xét mô hình công ty sau đây.

Có ~n~ người làm việc cho một công ty phần mềm lớn. Mỗi người thuộc một phòng ban nào đó. Ban đầu, mỗi người làm việc cho dự án của riêng mình trong phòng ban của mình (do đó, công ty ban đầu bao gồm ~n~ phòng ban, mỗi phòng ban có một người).

Tuy nhiên, thời điểm khó khăn đã đến với công ty và ban quản lý phải thuê một người quản lý khủng hoảng để xây dựng lại quy trình làm việc nhằm tăng hiệu quả. Chúng ta hãy sử dụng nhóm (người) để đại diện cho một nhóm mà một số người cùng làm việc. Người quản lý khủng hoảng có thể đưa ra hai loại quyết định:

1. Gộp phòng ban của nhóm ( ~x~ ) và nhóm ( ~y~ ) thành một phòng ban lớn chứa tất cả nhân viên của nhóm ( ~x~ ) và nhóm ( ~y~ ), trong đó ~x~ và ~y~ (~1 \le x \le y \le n~) — là số của hai nhân viên trong một công ty. Nếu nhóm ( ~x~ ) khớp với nhóm ( ~y~ ) , thì không có gì xảy ra.

2. Gộp các phòng ban nhóm ( ~x~ ), nhóm ( ~x + 1~ ), ..., nhóm ( ~y~ ) , trong đó ~x~ và ~y~ (~1 \le x \le y \le n~) — là số của hai nhân viên trong một công ty.

Lúc đó, người quản lý khủng hoảng đôi khi có thể tự hỏi liệu nhân viên ~x~ và ~y~ (~1 \le x \le y \le n~) có làm việc cùng một phòng ban hay không.

Hỗ trợ người quản lý khủng hoảng và trả lời mọi thắc mắc của họ.

Input

Dòng đầu tiên của dữ liệu đầu vào chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 200 000~, ~1 \le q \le 500 000~) — số lượng nhân viên của công ty và số lượng truy vấn mà người quản lý khủng hoảng có.

Các dòng q tiếp theo chứa các truy vấn của người quản lý khủng hoảng. Mỗi truy vấn trông giống như loại ~x~ ~y~, trong đó ~1 \le \textit{loại} \le 3~. Nếu loại = 1 hoặc loại = 2 , thì truy vấn biểu thị quyết định của người quản lý khủng hoảng về việc sáp nhập các phòng ban của loại thứ nhất và loại thứ hai tương ứng. Nếu loại = 3 , thì nhiệm vụ của bạn là xác định xem nhân viên ~x~ và ~y~ có làm việc tại cùng một phòng ban hay không. Lưu ý rằng ~x~ có thể bằng ~y~ trong truy vấn của bất kỳ loại nào.

Output

Đối với mỗi câu hỏi loại 3 , hãy in "YES" hoặc "NO" (không có dấu ngoặc kép), tùy thuộc vào việc những người tương ứng có làm việc trong cùng một phòng ban hay không.

Scoring

Sample Input 1

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

Sample Output 1

NO
YES
YES

Sample Input 2

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

Sample Output 2

YES
NO
YES

Cho một cây có ~n~ đỉnh. Ban đầu không có cạnh nào, mỗi đỉnh là gốc của chính đỉnh đó.

Bạn cần thực hiện hai loại truy vấn sau:

~\scriptsize \bullet~ Gốc ~a~ trở thành con của gốc ~b~ (và không còn là gốc nữa),

~\scriptsize \bullet~ Cho một node ~c~, in ra khoảng cách từ ~c~ đến gốc của nó.

Với truy vấn thứ hai, nếu ~c~ là gốc thì kết quả sẽ bằng 0, ngược lại kết quả sẽ là một số nguyên dương — độ "sâu" của node đó.

Viết chương trình giải quyết các truy vấn trên.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n, m \leq 3 \cdot 10^5)~ — số lượng đỉnh và số lượng truy vấn tương ứng.

~m~ dòng tiếp theo chứa các truy vấn. Truy vấn thứ nhất có dạng "~\texttt{1}~ ~a~ ~b~" ~(1 \leq a \neq b \leq n)~, trong đó ~a~ và ~b~ đều là các gốc. Truy vấn thứ hai có dạng "~\texttt{2}~ ~c~" ~(1 \leq c \leq n)~.

Output

Với mỗi truy vấn loại hai, in ra kết quả trên một dòng.

Scoring

Sample Input 1

10 20
1 9 4
1 2 6
2 10
1 10 5
2 5
1 7 4
1 8 5
2 1
1 6 5
1 3 5
1 1 4
1 5 4
2 7
2 2
2 4
2 3
2 4
2 2
2 2
2 10

Sample Output 1

0
0
0
1
3
0
2
0
3
3
2