시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB1000.000%

문제

How do setters come up with problems? Sometimes they just take a couple of buzzwords and smash them together. But we are in 2024, so this totally can be outsourced to AI. Introducing our creation based on ChatGPT: RICH B! And its second official problem:

Prompt: Minimum Spanning Tree

Problem: A complete graph with $n$ nodes and $\frac{n \cdot (n - 1)}{2}$ edges is chosen. Each edge is randomly assigned a real-valued weight within the range of $[0, 1]$. Your task is to find its minimum spanning tree. But you are not given the edges. Instead, you can make queries of the form "? $v_1$ $u_1$ $v_2$ $u_2$", and the jury program will respond to you with $1$ if the weight of edge $(v_1, u_1)$ is less than the weight of edge $(v_2, u_2)$, and it will respond with $0$ if it's not.

When you think that you know the minimum spanning tree, print it as "! $v_1$ $u_1$ $v_2$ $u_2$ $\ldots$ $v_{n - 1}$ $u_{n - 1}$", where edges $(v_i, u_i)$ form the minimum spanning tree. Constraints: $2 \le n \le 100$, and you can make at most $6000$ queries.

인터랙션 프로토콜

First, read a line that contains a single $n$ ($2 \le n \le 100$): the size of the graph.

To compare two edges, print a single line in the following format: "? $v_1$ $u_1$ $v_2$ $u_2$". You will then have to read a line with the result of the comparison: $1$ if the weight of the first edge is less than the weight of the second edge, or $0$ otherwise.

To output the answer, print a single line in the following format: "! $v_1$ $u_1$ $v_2$ $u_2$ $\ldots$ $v_{n - 1}$ $u_{n - 1}$". Your program has to immediately terminate after printing this line, otherwise, you may get unpredictable verdicts.

In every line you print, $(v_i, u_i)$ should be pairs of integers where $1 \le v < u \le n$), otherwise, you may get unpredictable verdicts.

Your program should not make more than $6000$ comparisons.

예제 입력 1

3

1

1

예제 출력 1


? 1 2 1 3

? 1 3 2 3

! 1 2 1 3

힌트

The Minimum Spanning Tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible total weight.

A spanning tree is a connected subgraph of the given graph that contains all of the graph's vertices and does not contain cycles.

The interactor is not adaptive.

Remember to end the line and flush the output after every line you print. To flush the output, you can use fflush(stdout) in C/C++, System.out.flush() in Java, or sys.stdout.flush() in Python.

채점 및 기타 정보

  • 예제는 채점하지 않는다.