Đây là một bài toán tương tác.

Trên hành tinh KSA có $N$ hòn đảo. Các hòn đảo được đánh số từ $1$ đến $N$, và hòn đảo $i$ có $w_i$ tài nguyên. Không có hai hòn đảo nào có cùng lượng tài nguyên. Giữa các hòn đảo có $N-1$ đường đi ngầm hai chiều, và đảm bảo rằng bất kỳ hai hòn đảo nào cũng có thể đi đến nhau chỉ bằng các đường đi ngầm. Nói cách khác, cấu trúc được tạo bởi các hòn đảo và các đường đi ngầm là một cây.

Sau khi nhận ra rằng các đường đi ngầm trên hành tinh KSA không thể nhìn thấy từ các hành tinh khác, Alice, vua của hành tinh KSA, dự định xây dựng thêm $N-1$ cây cầu mặt đất hai chiều nối các cặp hòn đảo. Chỉ sử dụng các cây cầu này, cũng phải có khả năng đi lại giữa bất kỳ hai hòn đảo nào. Nghĩa là, cấu trúc cây cầu cũng phải tạo thành một cây.

Sau khi Alice xây dựng xong các cây cầu, Bob, vua của hành tinh Automata, bắt đầu cố gắng khám phá thông tin. Tại thời điểm này, các số hiệu hòn đảo được gán lại một cách tùy ý, và kể từ đó, mọi số hiệu hòn đảo mà Bob quan sát hoặc sử dụng đều tuân theo hệ thống đánh số đã được gán lại này.

Bob phải xác định $x(i,j)$ cho tất cả $1 \le i,j \le N$ chỉ bằng cách nhìn vào các cây cầu mặt đất do Alice xây dựng, trong đó:

Ở đây, số hiệu hòn đảo bắt đầu $i$, hòn đảo đích $j$, và số hiệu của hòn đảo có lượng tài nguyên lớn nhất đều dựa trên hệ thống đánh số đã được gán lại. Đường đi từ hòn đảo số $i$ đến hòn đảo số $j$ bao gồm cả hòn đảo số $i$ và hòn đảo số $j$.

Trước khi xác định tất cả các giá trị của $x(i,j)$, Bob có thể đặt câu hỏi sau tối đa $100$ lần để lấy thêm thông tin:

• `?` $i$ $j$ : $x(i,j)$ là gì?

Vì giao tiếp liên hành tinh rất đắt đỏ, số lượng câu hỏi ít hơn sẽ dẫn đến điểm số cao hơn.

Chương trình của bạn được thực thi hai lần cho mỗi dữ liệu chấm. Trong lần thực thi đầu tiên, nó phải đóng vai Alice, và trong lần thực thi thứ hai, nó phải đóng vai Bob.

Dòng đầu tiên chứa một số nguyên $S$, biểu thị bước thực thi. $S=1$ nghĩa là đóng vai Alice, và $S=2$ nghĩa là đóng vai Bob.

Dữ liệu vào bao gồm một hoặc nhiều bộ test. Dòng thứ hai chứa số lượng bộ test, $T$. Mỗi bộ test được cho như sau:

Dòng đầu tiên chứa số lượng hòn đảo, $N$.

Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $w_1, w_2, \cdots, w_N$.

Mỗi dòng trong $N-1$ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách $u$, $v$, là hai đầu mút của một đường đi ngầm.

Vai trò của Alice

Xuất ra $N-1$ dòng, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách $u$ và $v$ là hai đầu mút của một cây cầu mặt đất cần xây dựng. Thứ tự các cây cầu được in ra không quan trọng, và thứ tự của hai đầu mút trong mỗi cây cầu cũng không quan trọng.

Vai trò của Bob

Dữ liệu vào bao gồm một hoặc nhiều bộ test. Dòng thứ hai chứa số lượng bộ test, $T$. Mỗi bộ test được cho như sau:

Dòng đầu tiên chứa số lượng hòn đảo, $N$.

Mỗi dòng trong $N-1$ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách $u$, $v$, là hai đầu mút của một cây cầu mặt đất do Alice xây dựng. Lưu ý rằng $u$ và $v$ sử dụng hệ thống đánh số đã được gán lại, và thứ tự các cây cầu mà Bob nhận được có thể khác với thứ tự Alice đã in ra.

Để biết thêm thông tin, khi truy vấn sau được in ra, dòng tiếp theo sẽ chứa giá trị của $x(i,j)$. Truy vấn này có thể được sử dụng tối đa $100$ lần cho mỗi bộ test.

• `?` $i$ $j$ ($1 \le i, j \le N$)

Để gửi câu trả lời, in `!` , và sau đó in câu trả lời trong $N$ dòng tiếp theo. Trên dòng thứ $i$ trong $N$ dòng, $x(i,1), x(i,2), \cdots, x(i,N)$ phải được in cách nhau bởi dấu cách. Truy vấn này không tính là một câu hỏi, và quá trình tương tác cho bộ test tương ứng kết thúc ngay sau khi in.

Nếu quá trình tương tác kết thúc cho một bộ test không phải là bộ cuối cùng, chương trình phải chuyển ngay sang bộ test tiếp theo. Nếu quá trình tương tác cho bộ test cuối cùng kết thúc, chương trình phải kết thúc ngay lập tức.

Tuy nhiên, nếu có hơn $100$ câu hỏi được đặt ra trong một bộ test, phản hồi cho truy vấn sẽ là `-1` , cho biết đã vượt quá số lượng câu hỏi cho phép. Trong trường hợp này, chương trình của bạn phải kết thúc ngay lập tức, và kết quả sẽ bị đánh giá là Wrong Answer.

Giới hạn

• $S \in \{1, 2 \}$
• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le u < v \le N$
• $1 \le w_i \le 10^9$
• Nếu $i \ne j$, thì $w_i \neq w_j$

Chấm điểm

Đối với mỗi dữ liệu chấm, gọi $Q$ là số lượng câu hỏi tối đa được đặt ra trong tất cả các bộ test. Điểm số cho dữ liệu chấm đó được xác định như sau:

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1 4
2 3
3 4

Dữ liệu vào 2

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

Dữ liệu ra 2

? 2 3

? 1 2

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

? 1 2

!
1 2
2 2

Ghi chú

Trong Ví dụ 1, vì $S = 1$, chương trình của bạn phải đóng vai Alice.

Trong Ví dụ 2, vì $S = 2$, chương trình của bạn phải đóng vai Bob.

Trong bộ test đầu tiên, các đỉnh $1, 2, 3, 4$ từ lần thực thi đầu tiên đã được gán lại thành các đỉnh $2, 4, 1, 3$ tương ứng.

Trong bộ test thứ hai, các đỉnh $1, 2$ từ lần thực thi đầu tiên đã được gán lại thành các đỉnh $2, 1$ tương ứng.

Bạn phải xóa bộ đệm đầu ra (flush) ngay sau khi in bất cứ thứ gì. Để xóa bộ đệm, bạn có thể sử dụng:

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• Đọc tài liệu cho các ngôn ngữ khác.

Ngoài ra, lưu ý rằng các dòng trống trong ví dụ đầu vào và đầu ra chỉ để cho rõ ràng, và không xuất hiện trong quá trình tương tác thực tế.