아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Team order

시간 제한6초메모리 제한256 MB

요약
각 팀이 사용할 수 있는 이름 집합이 주어질 때, 이름을 사전순으로 정렬한 뒤 팀 순서가 모든 순열이 될 수 있는지 판정하고, 불가능한 순열 하나를 출력한다.
난이도

보통10점 중 6점

유형
그래프, 위상 정렬, 정렬
정답자
아직 제출이 없습니다

문제

NN teams are planning to go to the All-Siberian Programming Contest, but none of them has registered yet. After the registration, teams are sorted lexicographically by their names. The contest jury want to know the order of the teams in the list. They did a little study. Having studied the teams' performance at other contests, the jury have compiled a list of possible names for every team. They found that the team with the number ii could use any of its favorite names S_i1,…,S_iK_iS\_{i1}, \dots, S\_{iK\_i} to register.

Here comes the question. Is it true that their little study is absolutely worthless? In other words, is it true that teams can end up in the list in any order? If this is wrong, the jury at least wants to know a single order of the teams which would be impossible.

입력

The first line of the input file contains a single integer NN  --- the number of teams (1≤N≤3501 \leq N \leq 350). It is followed by NN blocks of lines, each describing a team. Teams are numbered from 11 to NN in the order as they are described in the input file.

The first line of the description of the ii-th team contains a single integer positive number K_iK\_i. The description block of the ii-th team consists of K_i+1K\_i+1 lines, including the line with the number K_iK\_i. The following K_iK\_i lines contain the possible names of the ii-th team, one per line: S_i1,…,S_iK_iS\_{i1}, \dots, S\_{iK\_i}. A team name can only contain lowercase Latin letters. Each name is non-empty and is not longer than 100100 characters. All K_iK\_i names are distinct.

It is guaranteed that different teams do not have matching names. It is also guaranteed that ∑_i=1NK_i≤350\sum\limits\_{i=1}^NK\_i\leq350.

출력

If the teams names can end up in the list in any order, print the word YES in the output file.

Otherwise, print the word NO in the first line; in the second line, print any impossible teams order as a list of NN space-separated integers. Here kk-th integer is the number of the team being kk-th in the lexicographically sorted list of names.

예제2

  1. 예제 1

    입력
    3
    1
    teamname
    2
    vanechka
    ivan
    4
    albatross
    teddybear
    vitalya
    pythonists
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2
    2
    geometrylovers
    epsiszero
    1
    speedcoderz
    
    예상 출력
    NO
    2 1