프로그램 명: usa_gdisc
제한시간: 1 초

//작업 중... Bessie has a created a puzzle for Farmer John. In front of him there is a lake with N (1 <= N <= 40) small islands, with bridges between some pairs of islands. Bessie has agreed to tell FJ if it is possible to safely get from any island to any other island *without* using a specified set of bridges.

That is, if we think of the islands as a graph, with bridges corresponding to edges, then Bessie will tell FJ if all N vertices are connected *after removing a specified subset of the edges*. (It is guaranteed that the initial graph is connected.)

FJ would like to determine exactly which bridges exist. Help FJ figure this out using as few questions as possible (see below for a detailed description of the scoring procedure).

An example dialogue between Bessie and FJ might be as follows, assuming that the collection of islands corresponds to the graph on 4 vertices consisting of edges {{1,2}, {1,3}, {1,4}, {2,3}} (depicted below): 

1--2
|\ |
| \|
4  3

FJ's query      |  Bessie's response   |  Comments
------------------------------------------------------------------------
{{1,2}}         |     Yes              |
{{3,4}}         |     Yes              |
{{1,4}, {4,3}}  |     No               | {1,4} must be an edge
{{1,2}, {2,3}}  |     No               | {2,3} must be an edge
{{1,2}, {3,1}}  |     No               | {1,3} must be an edge
{{1,3}}         |     Yes              | {1,2} must be an edge
{{1,4}}         |     No               | {2,4} and {3,4} are not edges
FJ can then conclude that the graph has edges {{1,2}, {1,3}, {1,4}, {2,3}}, and no others.

This problem is a reactive problem, meaning that instead of reading and writing to a file you will use stdin and stdout (in other words, console input and output) to interact with a grader program. See the input description for important information about interactive problems.

At the beginning of execution, the grader program will write a single integer, N, the number of vertices. You will then write lines with one of the following three forms: 

R i j
U i j
Q
where R, U, and Q are the characters 'R', 'U', and 'Q', and i and j are integers in the range 1..N. The first sort of query removes the edge between vertices i and j (if it exists). The second undoes the previous removal of an edge between i and j. The third asks whether the graph is connected; after you output Q, the grader will output either 0 (for not connected) or 1 (for connected).

When your program is ready to output the graph, you should output a line with the single character 'A', then N lines, each with N characters. The jth number on the ith of these lines should be 1 if vertices i and j are adjacent, and 0 otherwise (a vertex is never adjacent to itself).

If you output an incorrect graph at the end, you will receive 0 points. Otherwise, you will receive points based on the number of times you output 'Q'. If you output 'Q' at most 900 times then you will receive 100% of the points. If you output 'Q' K times for some 900 < K <= 5000, then you will receive a percentage of the points equal to 20+80*(900/K). If you output 'Q' more than 5000 times, you will receive 0 points.

A dialogue corresponding to the example above is as follows (< indicates the grader's output, > indicates your program's output; these symbols are for clarity only and not part of the actual output). 

I/O        | Set of removed edges
----------------------------------
< 4        |
> R 1 2    | {{1,2}}
> Q        |
< 1        |
> U 1 2    | {}
> R 3 4    | {{3,4}}
> Q        |
< 1        |
> R 4 1    | {{3,4}, {4,1}}
> Q        |
< 0        |
> U 3 4    | {{4,1}}
> U 1 4    | {}
> R 1 2    | {{1,2}}
> R 2 3    | {{1,2}, {2,3}}
> Q        |
< 0        |
> U 3 2    | {{1,2}}
> R 3 1    | {{1,2}, {3,1}}
> Q        |
< 0        |
> U 1 2    | {{3,1}}
> Q        |
< 1        |
> U 3 1    | {}
> R 1 4    | {{1,4}}
> Q        |
< 0        |
> A        |
> 0111     |
> 1010     |
> 1100     |
> 1000     |
TIME LIMIT: 2 seconds

Interactive programs usually require extra code that causes output to be unbuffered -- to be written in real time instead of buffering for faster (but later) output.

Those C/C++ users who use #include should execute this line before any input or output:

setlinebuf (stdout);

Users of should also use fgets () to read from stdin. Use of scanf is not recommended; do something like this to parse input data: 

    char line[1000];
    setlinebuf (stdout);

    fgets (line, 1000, stdin);
    sscanf (line, "..format..", &var1, ...);
    /* if the line contents need to be interpreted */
Those C++ users who use iostream should cout << flush after each line (and also use cin in the normal manner): 
    cout << foo << endl;
    cout << flush;
Be sure when you read the response from the computer that you read *all* the letters, not just the first one. The response will never be more than one letter + one newline + one string terminator ('\0'). import java.io.*; ... PrintStream out = new PrintStream (System.out, true); // 'unbuffers' output ... // sample integer print: out.println (foo);

For Pascal, use the following scheme for writing: 

    writeln (stdout, ...your output here...); flush(stdout);


Be sure to read in the entire reply -- make room for the letter,
the newline, and the string terminator.


Despite the references to gdisc.in and gdisc.out here and below, no files are
used for input or output.


INPUT FORMAT:

SAMPLE INPUT 

OUTPUT FORMAT:

SAMPLE OUTPUT 




입력



출력



입출력 예



입력

출력





출처:





[질/답]
[제출 현황]
[푼 후(0)]


[홈으로]  [뒤 로]