패키지

Vinux OS에서 패키지를 설치할 때 Vasya는 현대적인 패키지 관리자인 Vum을 사용한다.

각 패키지에는 설치할 수 있는 여러 버전이 있다. 한 번에 한 버전만 설치할 수 있다. 특정 애플리케이션의 특정 버전을 패키지라고 부르자. 서로 다른 애플리케이션의 특정 버전끼리 호환되지 않을 수 있기 때문에 Vum에는 충돌이라는 개념이 있다. 모든 충돌은 패키지의 집합이며, 그중 하나만 설치할 수 있다. 충돌 목록에 있는 패키지를 두 개 이상 설치하려고 하면 충돌이 발생하며, Vasya는 이를 원하지 않는다.

모든 애플리케이션의 서로 다른 버전끼리 충돌할 수도 있고 그렇지 않을 수도 있다. 애플리케이션의 여러 버전이 하나의 충돌에 포함될 수 있으며, 애플리케이션의 모든 버전이 포함될 수도 있다.

Vum의 충돌 설명 시스템은 다소 원시적이기 때문에 각 패키지는 하나의 충돌에만 나열될 수 있다.

Vasya는 Vinux를 충돌 없이 사용하면서 $N$개의 서로 다른 애플리케이션을 설치하려고 한다. 위의 규칙을 어기지 않으면서 애플리케이션 버전을 선택해야 하지만, Vum의 철저한 의존성 해결 알고리즘으로는 이 작업을 처리할 수 없다. Vasya는 패키지 관리자에 대한 도움을 요청한다.

입력 파일의 첫 번째 줄에는 정수 $N$이 주어진다. 이는 Vasya가 설치하려는 애플리케이션의 수이다 ($1$ $\le$ $N$ $\le$ $200$).

다음 $N$개의 줄에는 애플리케이션의 설명이 주어지며, 각 설명은 버전 목록을 포함한다. 애플리케이션 설명은 공백으로 구분된 다음 필드로 구성된다:

• 애플리케이션 이름: 1자에서 10자 사이의 소문자 라틴 문자로 이루어진 문자열;
• 버전 수: $1\,000$ 이하의 양의 정수;
• 버전 번호: 오름차순으로 나열된 양의 정수.

애플리케이션의 번호는 $100\,000$ 이하이다. 모든 애플리케이션 이름은 서로 다르다.

다음 줄에는 충돌의 수 $K$가 주어진다 ($0$ $\le$ $K$ $\le$ $500$).

다음 $K$개의 줄에는 충돌이 설명된다. 충돌 설명은 충돌에 포함된 패키지의 수 $T$로 시작한다. 그다음 $T$개의 패키지가 공백으로 구분되어 나열된다. 각 패키지에 대해 애플리케이션 이름과 버전 번호가 주어진다.

충돌에 나열된 패키지는 중복되지 않으며, 모든 버전은 애플리케이션 설명에 언급되어 있다고 보장된다.

충돌 없이 $N$개의 애플리케이션을 모두 설치할 수 없다면, 출력 파일의 유일한 줄에 No라는 단어를 출력해야 한다. 가능하다면, 첫 번째 줄에 Yes라는 단어를 출력하고, 두 번째 줄에 설치해야 하는 버전 번호를 공백으로 구분하여 나열해야 한다.

$N$개의 애플리케이션에 대한 버전은 입력 파일에 설명된 애플리케이션의 순서와 동일한 순서로 출력해야 한다. 가능한 선택이 여러 개라면 그중 아무거나 출력해도 된다.

첫 번째 예제에는 두 개의 충돌이 있다. 첫 번째 충돌은 vim의 세 번째 버전과 nano의 여덟 번째 버전을 동시에 설치하는 것을 막는다. 두 번째 충돌은 다음 중 하나만 설치할 수 있음을 나타낸다: vim의 1번 버전, nano의 5번 버전, vim의 2번 버전, 또는 아무것도 설치하지 않음. 올바른 해는 다음과 같다:

• 1 8 2
• 1 8 3
• 2 8 2
• 2 8 3
• 3 5 2
• 3 5 3

두 번째 예제에는 두 개의 애플리케이션이 있으며, 각각 하나의 버전만 가진다. 그러나 유일한 충돌이 두 애플리케이션을 함께 설치하는 것을 금지한다.