Diverse Singing
시간 제한2초메모리 제한512 MB
각 가수와 각 곡이 최소 한 번씩 포함되고, 같은 가수-언어 쌍과 같은 곡-언어 쌍이 두 번 쓰이지 않도록 레퍼토리 항목을 고르는 문제이며, 불가능하면 -1을 출력한다.
문제
In the modern world, diversity is the major concern, language diversity in particular. That’s why the upcoming talent show is going to be held in multiple languages. However, making the program both diverse and not boring is a tough problem.
There are n singers going to participate in the show and m songs to be performed. Each singer has several songs in their repertoire, and some of them may be sung in different languages. For a program to be complete, each participant should sing at least one song and each song should be sung at least once. For a program to be not boring, each participant should use each language no more than once, and each song should be sung in each language no more than once as well.
Given the repertoire of each singer, make a complete and not boring program of the show, or determine that it is impossible.
입력
In the first line of input, there are three integers n, m, k: the number of singers, songs and possible acts, respectively (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10 000).
The next k lines describe the repertoires. The i-th line contains three integers pi, si, li (1 ≤ pi ≤ n, 1 ≤ si ≤ m, 1 ≤ li ≤ k) denoting that the participant pi can sing the song si in the language li.
출력
If it is impossible to make a complete and not boring program, print a single number “-1” (without quotes).
Otherwise, on the first line, print an integer t: the number of songs to be performed. On the second line, print t distinct integers between 1 and k: the repertoire entries to include in the program. The entries are numbered from 1 in the order they are given in the input. The repertoire entries can be printed in any order. If there are several possible answers, print any one of them.