/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは、N 人のユーザが参加する SNS を運営している。彼らはユーザ 1, \ldots, N と呼ばれ、別のユーザを何人でもフォローすることができる。
しかし、あるトラブルにより、どのユーザがどのユーザをフォローしているかの情報がすべて失われてしまった。幸い、ユーザがこの SNS で行ったすべての操作のログが残っており、あなたは操作ログをもとにフォロー状況を復元しようとしている。
操作ログは Q 行からなり、その i 行目 (1 \leqq i \leqq Q) は文字列 S_i である。各ユーザは以下の 3 種類の操作を行うことができ、S_i は SNS 全体で i 番目に行われた操作に対応する。
- フォロー: ユーザ a がユーザ b (a \neq b) をフォローする。ログには
1 a bという行が記載される。 - フォロー全返し: ユーザ a が、その時点でユーザ a をフォローしているユーザ全員をフォローする。ログには
2 aという行が記載される。 - フォローフォロー: その時点でユーザ a がフォローしている各ユーザ x に対し、ユーザ a が次を行う: 「その時点でユーザ x がフォローしているすべてのユーザ (ユーザ a 自身を除く) をフォローする」。ログには
3 aという行が記載される。
なお、この SNS が開設された時点では、どのユーザも誰もフォローしていなかった。また、ユーザ a がユーザ b を既にフォローしているとき、ユーザ a がユーザ b を再びフォローしても何も起こらない。
フォロー状況を復元せよ。
制約
- 2 ≦ N ≦ 100
- 0 ≦ Q ≦ 500
- S_i は以下のいずれかの形式の文字列である。
1 a b(1 \leqq a, b \leqq N かつ a \neq b)2 a(1 \leqq a \leqq N)3 a(1 \leqq a \leqq N)
入力
入力は以下の形式で標準入力から与えられる。
N Q S_1 S_2 : S_Q
出力
各 i, j (1 \leq i, j \leq N) に対し、ユーザ i がユーザ j をフォローしているとき f_{i,j} = Y, そうでないとき f_{i,j} = N として、以下の形式で出力せよ。
f_{1,1}f_{1,2} \ldots f_{1,N}
f_{2,1}f_{2,2} \ldots f_{2,N}
:
f_{N,1}f_{N,2} \ldots f_{N,N}
入力例 1
6 7 1 1 2 1 2 3 1 3 4 1 1 5 1 5 6 3 1 2 6
出力例 1
NYYNYY NNYNNN NNNYNN NNNNNN NNNNNY YNNNYN
6 人のユーザ、ユーザ 1, \ldots, 6 が合計で 7 回の操作を行い、以下のようなログが残されている。
- S_1: ユーザ 1 がユーザ 2 をフォローした。
- S_2: ユーザ 2 がユーザ 3 をフォローした。
- S_3: ユーザ 3 がユーザ 4 をフォローした。
- S_4: ユーザ 1 がユーザ 5 をフォローした。
- S_5: ユーザ 5 がユーザ 6 をフォローした。
- S_6: ユーザ 1 がフォローフォローを実行した。操作が行われる時点でユーザ 1 がフォローしているユーザはユーザ 2, 5 の二人であり、ユーザ 2 はユーザ 3 を、ユーザ 5 はユーザ 6 をフォローしている。よって、ユーザ 1 はユーザ 3, 6 の二人をフォローする。
- S_7: ユーザ 6 がフォロー全返しを実行した。操作が行われる時点でユーザ 6 をフォローしているユーザはユーザ 1, 5 の二人であり、ユーザ 6 はこの二人をフォローする。
最終的に、フォロー状況は出力例の通りとなる。
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You run a social media site with N users. The users are called User 1, \ldots, N, and they can follow an unlimited number of other users. The list of users followed by a particular user is called follow-list of that user.
However, due to trouble, the follow-lists of all users have been lost. Fortunately, all operations ever performed on the site have been recorded in the log file. You are trying to restore the follow-lists of the users from this file.
The file consists of Q lines, and the i-th line contains a string S_i. The users can perform the three kinds of operations below, and S_i corresponds to the i-th operation performed on the whole site.
- Follow: User a follows User b (a \neq b). The log file records the line
1 a b. - Follow-Back-All: User a follows all users who are following User a at that moment. The log file records the line
2 a. - Follow-Follow: For every user x who are followed by User a at that time, User a performs the following: "follow all users (except User a itself) followed by User x." The log file records the line
3 a.
At the beginning of the site, no user was following anyone else. Also, if User a is already following User b and attempts to re-follow User b, nothing happens.
Restore the follow-lists of all users.
Constraints
- 2 \leq N \leq 100
- 0 \leq Q \leq 500
- S_i is a string in one of the following formats:
1 a b(1 \leq a, b \leq N and a \neq b)2 a(1 \leq a \leq N)3 a(1 \leq a \leq N)
Input
Input is given from Standard Input in the following format:
N Q S_1 S_2 : S_Q
Output
For each pair i, j (1 \leq i, j \leq N), let f_{i,j} = Y if User i follows User j and f_{i,j} = N otherwise. Output should be in the following format:
f_{1,1}f_{1,2} \ldots f_{1,N}
f_{2,1}f_{2,2} \ldots f_{2,N}
:
f_{N,1}f_{N,2} \ldots f_{N,N}
Sample Input 1
6 7 1 1 2 1 2 3 1 3 4 1 1 5 1 5 6 3 1 2 6
Sample Output 1
NYYNYY NNYNNN NNNYNN NNNNNN NNNNNY YNNNYN
Six users, User 1, \ldots, 6, performed a total of seven operations, which resulted in the following log file:
- S_1: User 1 followed User 2.
- S_2: User 2 followed User 3.
- S_3: User 3 followed User 4.
- S_4: User 1 followed User 5.
- S_5: User 5 followed User 6.
- S_6: User 1 performed Follow-Follow. At the moment, User 1 was following two users, User 2 and 5. User 2 was following User 3, and User 5 was following User 6, so User 1 followed two users, User 3 and 6.
- S_7: User 6 performed Follow-Back-All. At the moment, User 6 was followed by two users, User 1 and 5, so User 6 followed back these two users.
In the end, we have the follow-lists shown in the output above.