#1906 twitter.com

32  20 s   256 MB  

Description

이번 과제는 현재 유행하는 SNS인 twitter.com 의 following system의 일부를 구현하는 과제다.
 
만약 임의의 사용자 X가 Y라는 사용자를 following 할 경우 사용자 X의 time-line(시간 순으로 글이 올라오는 장소) 에서는 Y가 올린 글을 볼 수 있다.
 
이번 과제는 총 N명의 twitter.com 사용자가 존재할 때, Q개의 명령을 처리하는 프로그램을 작성하는 것이다. 명령의 종류는 아래 Input의 설명을 참고하도록 한다.
 

Input

입력의 첫줄에는 사용자의 수 N ( 1 ≤ N ≤ 1,000,000 ) 과 명령의 수 Q ( 1 ≤ Q ≤ 100,000 ) 가 입력된다.

 
명령은 두가지 종류로 다음과 같다.
각 명령에 입력된 사용자 A가 follow 하는 사람들의 수와 명단을 출력해야한다. 만약 follow 하는 사용자의 수가 10명을 넘을 경우 수는 그대로 출력하고, 명단은 사용자 번호 기준 오름차순으로 정렬했을 때 10번째 사용자 까지 출력한다.
 
주의 : 1인당 following 할 수 있는 사람의 수는 최대 5000명이다. 그 이상의 수를 following 하는 경우는 입력으로 들어오지 않는다.
 

Output

출력형식은 다음과 같다.

<X> M : A1,A2,...,AM
X는 follwing을 하거나 unfollowing을 하는 사용자를 뜻하며, M 은 follow 하고 있는 사람의 수를 뜻하며, A1, A2, ..., AM은 오름차순 기준으로 첫번째, 두번째, ..., M번째 사용자를 뜻한다.
만약 following 하는 사람이 하나도 없을 경우 <X> NONE을 출력한다.
 

Sample Input

Sample Output

3 6
F 1 2
F 0 1
F 0 2
U 0 1
U 0 2
F 1 0
<1> 1 : 2
<0> 1 : 1
<0> 2 : 1,2
<0> 1 : 2
<0> NONE
<1> 2 : 0,2