문제
승석이는 동성이와 함께 고급 레스토랑에 가서 근사한 음식을 먹고 싶어한다. 하지만 동성이는 분식집에 가서 음식을 먹기를 원한다.
승석이와 동성이가 있는 도시는 N개의 교차로가 있으며 각 교차로의 이름은 a, b, c, …, n으로 알파벳 소문자 형태로 이루어졌다.
고급 레스토랑은 교차로 a에 위치해 있다.
승석이와 동성이는 이 도시의 지리를 모르기 때문에 승석이가 우선 자신이 있는 위치에서 출발하는 교통수단 중 무엇을 탈지 선택한다.
그러면 동성이는 그 교통수단을 타고 자신이 원하는 위치로 이동한다.
승석이는 최대한 빨리 고급 레스토랑에 도착하기 위해서 최선의 전략을 선택한다. 하지만, 동성이는 승석이가 최대한 늦게 고급 레스토랑에 도착하게 하기 위해 최선의 전략을 선택한다.
도시와 교통수단의 정보가 주어졌을 때 승석이와 동성이가 고급 레스토랑까지 가면서 이용하는 교통수단의 수를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 교차로의 수 N이 주어진다. (1 ≤ N ≤ 25)
두 번째 줄부터 N개의 줄에는 교차로 a, b, …, n에 대하여 해당 교차로에서 출발하는 교통수단의 수 M (1 ≤ M ≤ 2^N)이 주어지고, 해당 교차로에서 출발하는 M개의 교통수단에 대해서 갈 수 있는 교차로의 이름이 알파벳 순서대로 문자열로 주어진다. M개의 교통수단의 목적지에 해당되는 문자열들은 서로 다르다.
문제에서 주어지는 교통수단의 수의 총합은 1,000,000을 넘지 않는다.
출력
첫 번째 줄에 승석이와 동성이가 각각 교차로 a, b, …, n에서 출발했을 때 고급 레스토랑까지 가면서 이용하는 교통수단의 수를 출력한다.
만약 동성이가 승석이를 고급 레스토랑으로 가지 못하게 하는 방법이 있다면 -1을 출력한다.
예제 #1
3
1 b
2 b a
2 ab ac
0 1 2
예제 #2
4
1 cd
2 b ad
2 ab a
1 bc
0 -1 1 -1
힌트
출처
ACM-ICPC World Finals 2014 문제 D
로그인해야 코드를 작성할 수 있어요.