Problem:


		
Problem F: Gather the Maps!

		

			はるか昔、八尾氏が残したとされる伝説の秘宝が八王子のどこかに眠っているという。 その在処を示すとされる宝の地図は、いくつかの断片に分割された状態で、八尾氏の n 人の子孫達によって受け継がれている。
		

		

			今、八尾氏の子孫達は協力してその秘宝を手に入れようとしていた。 ところが、秘宝の在処を指し示す宝の地図の一部分だけでは秘宝を見つけることができない。 そこで、八尾氏の子孫達は全員で集まって地図を 1 ヶ所に集めようとした。
			ところが、いざ実行に移そうとしてもなかなか予定が合わずに集まることができない。 しかしこの秘宝に関する情報は、一族において秘密裏に伝えられてきた貴重な情報である。 漏洩の危険性を考慮すると、公共の通信手段を用いて地図をやりとりすることなど問題外である。
		

		

			そこで、子孫同士が直接会って地図を手渡すということを繰り返すことで、ある 1 人の子孫のところに地図を集めることにした。
			なお、1 人が 1 日に会える人数に制限はないが、互いにスケジュールが空いていることが必要である。
		

		

			あなたの仕事は、それぞれの子孫に対するスケジュールの空いている日のリストから、地図を集めるには最低で何日必要かを求めるプログラムを書くことである。
		

		

			ちなみに、八尾氏一族の結束は非常に固い。 最終的に地図全体を手にした子孫が、他の子孫を裏切って秘宝を持ち逃げすれば、一族から制裁を受けることになる。その制裁はきわめて恐ろしいものであるため、実際にその子孫が秘宝を持ち逃げすることは事実上不可能である。
		

		
Input

		

			入力は複数のデータセットからなる。
		

		

			それぞれのデータセットは複数の行からなる。 その最初の行には、地図の断片を持った者の人数を表す整数 n (1 < n <= 50) が記述されている。 続く n 行には、それぞれの子孫のスケジュールが書かれている。
			i 行目は i 人目の子孫のスケジュールが表しており、いくつかの整数が 1 文字のスペースを区切りとして書かれている。
			最初の整数 fi (0 <= fi <= 30) は、その子孫のスケジュールが空いている日の日数を表す整数である。 続く fi 個の整数は、スケジュールが空いている日付を表す。 これらの日付は互いに異なり、全て 1 以上 30 以下である。
		

		

			入力の最後に 0 のみを含んだ 1 行がある。
		

		
Output

			

				各データセットに対して、1 つの整数を 1 行に出力せよ。
				もし、30 日以内に地図を集めることができる場合は、地図を集めるのに最低限必要となる日数を、集めることができない場合は -1 を出力せよ。
			

			

				追記 :
				上記の「地図を集めるのに最低限必要となる日数」は 1 日を起点として最も早く全ての地図が集まる日付を意味する．
			

		
Sample Input

		

4
1 1
2 2 3
2 1 2
3 3 4 5
0

		
Output for the Sample Input

		

3



Sample input:
4
1 1
2 2 3
2 1 2
3 3 4 5
0


Sample output:
3

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = [LI()[1:] for _ in range(n)]
        d = collections.defaultdict(list)
        for i in range(n):
            for c in a[i]:
                d[c].append(i)
        r = -1
        s = [set([i]) for i in range(n)]
        for k in sorted(list(d.keys())):
            ts = set()
            for c in d[k]:
                ts |= s[c]
            if len(ts) == n:
                r = k
                break
            for c in d[k]:
                s[c] |= ts
        rr.append(r)

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
while N:
    days = [[] for _ in range(31)]
    roles = [2**i for i in range(N)]
    for i in range(N):
        for j in list(map(int, input().split()))[1:]:
            days[j].append(i)

    for i, day in enumerate(days):
        role = 0
        for d in day:
            role |= roles[d]
        for d in day:
            roles[d] = role
        if role == 2**N - 1:
            print(i)
            break
    else:
        print(-1)
    N = int(input())

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  days = [[] for _ in range(31)]
  for i in range(n):
    hima = list(map(int, input().split()))
    for d in hima[1:]:
      days[d].append(i)
  
  tos = [{i} for i in range(n)]
  end = {i for i in range(n)}
  for i in range(31):
    gather = set()
    for to in days[i]:
      gather = gather | tos[to]
    if gather == end:
      print(i)
      break
    for to in days[i]:
      tos[to] = gather
  else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
R = lambda:map(int,raw_input().split())
def solve(s,f):
    for i in xrange(30):
        c = []
        for j in xrange(n):
            if f[j][i+1] is True:
                c.append(j)
            #print sys.stderr, i,c
        if len(c) >= 2:
            for k in xrange(1,len(c)):
                #print sys.stderr, s
                s[c[0]].update(s[c[k]])
                #print sys.stderr, s[c[0]],s[c[k]]
                #print sys.stderr, s
            for k in xrange(1,len(c)):
                #print sys.stderr, s
                #print c[k]
                s[c[k]] = s[c[0]].copy()
        #print sys.stderr, s
        for j in xrange(n):
            if len(s[j]) is n: return i+1
    else: return -1
    
while 1:
    n = int(raw_input())
    if n is 0: break
    f = [[False for i in xrange(31)] for j in xrange(n)]
    s = [set() for i in xrange(n)]
    for i in xrange(n):
        m = R()
        for j in xrange(m[0]):
            f[i][m[j+1]] = True
    #print sys.stderr, s
    for i in xrange(n):
        s[i].add(i+1)
    #print sys.stderr, s
    print solve(s,f)

Submission status: Accepted

Solution code:
import sys
import collections

while True:
    n = int(raw_input())
    if n == 0:
        break
    
    state = []
    free = []
    for i in xrange(n):
        temp = map(int, raw_input().split())
        if temp[0] != 0:
            free.append(set(temp[1:]))
        else:
            free.append(set())
        state.append(set([i]))
    
    for i in xrange(1, 31):
        cand = []
        new = set()
        for j in xrange(n):
            if i in free[j]:
                cand.append(j)
                new |= state[j]
        for c in cand:
            state[c] = new
        if len(new) == n:
            print i
            break
    else:
        print -1

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = []
    while True:
        n = int(f_i.readline())
        if n == 0:
            break
        
        last_day = 1
        schedule = [set() for i in range(31)]
        
        for i in range(n):
            line = map(int, f_i.readline().split())
            f = next(line)
            
            for day in line:
                schedule[day].add(i)
                if day > last_day:
                    last_day = day
        
        groups = [set() for i in range(n)]
        for day in range(1, last_day + 1):
            member1 = schedule[day]
            member2 = member1.copy()
            for person in member1:
                member2 |= groups[person]
            
            if len(member2) == n:
                ans.append(day)
                break
            for person in member1:
                groups[person] |= member2
        else:
            ans.append(-1)
    
    print('\n'.join(map(str, ans)))

solve()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def c(n,d):
    return n+d*N

def dfs(s,n):
    global visited
    visited[s][n] = True
    for t in lines[s]:
        if not visited[t][n]:
            dfs(t,n)


while True:
    N = inp()
    if N == 0:
        break
    else:
        days = 30
        nds = [[False]*days for _ in range(N)]
        for n in range(N):
            tmpl = inpl()
            for i in range(1,tmpl[0]+1):
                nds[n][tmpl[i]-1] = True

        lines = defaultdict(set)
        cnt = 0
        for n in range(N):
            for d1 in range(days):
                for d2 in range(d1,days):
                    if nds[n][d1] and nds[n][d2]:
                        lines[c(n,d1)].add(c(n,d2))

        for d in range(days):
            for n1 in range(N):
                for n2 in range(n1,N):
                    if nds[n1][d] and nds[n2][d]:
                        lines[c(n1,d)].add(c(n2,d))
                        lines[c(n2,d)].add(c(n1,d))

        visited = [[False]*N for _ in range(c(N,days))]
        for n in range(N):
            for d in range(days):
                if nds[n][d]:
                    dfs(c(n,d),n)

        #print(visited)

        for b in range(N*days):
            for n in range(N):
                #print(b,n,visited[b][n])
                if visited[b][n]:
                    continue
                else:
                    break
            else:
                print(b//N+1)
                break
        else:
            print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque,defaultdict

def bfs(s):
    bfs_map = defaultdict(lambda : 1)
    bfs_map[s] = 0
    q = deque([s])
    b = defaultdict(lambda : 0)
    b[s[0]] = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs_map[y]:
                bfs_map[y] = 0
                q.append(y)
                b[y[0]] = 1

    for i in range(n):
        if not b[i]:
            return 0
    return 1

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    T = [[] for i in range(30)]
    v = defaultdict(list)
    for i in range(n):
        s = list(map(int, sys.stdin.readline()[:-1].split()))
        t = s[1:]
        t.sort()
        for j in t:
            T[j-1].append(i)
        for j in range(1,s[0]):
            v[(i,t[j]-1)].append((i,t[j-1]-1))
    f = 1
    for t in range(30):
        for i in range(len(T[t])-1):
            x = T[t][i]
            y = T[t][i+1]
            v[(x,t)].append((y,t))
            v[(y,t)].append((x,t))

    for t in range(30):
        if T[t]:
            if bfs((T[t][0],t)):
                f = 0
                print(t+1)
                break
        if not f:
            break
    if f:
        print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
while 1:
    n=int(input())
    if n==0:
        break
    dic={}
    ok=[[False for i in range(30)] for i in range(n)]
    for i in range(n):
        dic[i]=[i]
        for m in list(map(int,input().split()))[1:]:
            ok[i][m-1]=True
    f=False
    for i in range(30):
        tmp=[]
        for j in range(n):
            if ok[j][i]:
                tmp+=list(dic[j])
        tmp=set(tmp)
        for j in range(n):
            if ok[j][i]:
                dic[j]=list(tmp)
                if len(dic[j])==n:
                    print(i+1)
                    f=True
                    break
        if f:
            break
    if not f:
        print(-1)

Submission status: Runtime Error

Solution code:
from itertools import combinations
from decimal import Decimal

def get_point(line1, line2):
    m1, k1 = line1
    m2, k2 = line2
    if m1 == m2:
        return None    
    elif m1 is None and m2 is None:
        return None
    elif m1 is None:
        x = k1
        y = m2 * x + k2
    elif m2 is None:
        x = k2
        y = m1 * x + k1
    else:
        x = (k2-k1)/(m2-m1)
        y = m1*x+k
    if -100 < x < 100 and -100 < y < 100:
        return (x, y)
    else:
        return None

while True:
    N = int(input())
    if not N:
        break
    lines = []
    for i in range(N):
        x1, y1, x2, y2 = [Decimal(int(i)) for i in input().split()]
        if x1 == x2:
            lines.append(None, x1)
        else:
            m = (y2-y1) / (x2-x1)
            k = y1 - m * x1
            lines.append((m, k))
    
    iterated_lines = []
    ans = 1
    for line1 in lines:
        pt_set = set()
        for line2 in iterated_lines:
            pt = get_point(line1, line2)
            # print(pt)
            if pt:
                pt_set.add(pt)
        ans += len(pt_set) + 1
        iterated_lines.append(line1)
    print(ans)

Submission status: Runtime Error

Solution code:
while True:
    n = input()
    if (n == 0):
        break
    d = []
    for i in range(n):
        a = map(int, raw_input().split())
        d.append(a[1:])
    for i in range(31):
        ok = True
        for j in d:
            t = min(j)
            if (i < t):
                ok = False
                break
        if (ok):
            print i
            break
    if (ok):
        continue
    else:
        print -1

Submission status: Runtime Error

Solution code:
while True:
    n = input()
    if (n == 0):
        break
    d = []
    digit = set()
    for i in range(n):
        a = map(int, raw_input().split())
        for j in a[1:]:
            digit.add(j)
        d.append(a[1:])
    paper = [set() for i in range(n)]
    ans = 31
    for i in range(n):
        paper[i].add(i)

    for i in digit:
        for j in range(len(d)):
            if i in d[j]:
                for k in range(j, len(d)):
                    if i in d[k]:
                        for l in paper[k]:
                            paper[j].add(l)
                        for l in paper[j]:
                            paper[k].add(l)
        for j in range(len(d)):
            if (len(paper[j]) == n):
                ans = min(ans, i)

    if (ans != 31):
        print ans
    else:
        print -1

Submission status: Runtime Error

Solution code:
while True:
    n = input()
    if (n == 0):
        break
    d = []
    digit = set()
    for i in range(n):
        a = map(int, raw_input().split())
        for j in a[1:]:
            digit.add(j)
        d.append(a[1:])
    paper = [set() for i in range(n)]
    ans = 31
    for i in range(n):
        paper[i].add(i)
    for i in digit:
        for j in range(len(d)):
            if i in d[j]:
                for k in range(j, len(d)):
                    if i in d[k]:
                        for l in paper[k]:
                            paper[j].add(l)
                        for l in paper[j]:
                            paper[k].add(l)
        for j in range(len(d)):
            if (len(paper[j]) == n):
                ans = min(ans, i)
    if (ans != 31):
        print ans
    else:
        print -1

Submission status: Runtime Error

Solution code:
while(True):
    n = int(input())
    if n == 0:
        exit()
    d = []
    for i in range(n):
        ll = input().split()
        l = [int(_) for _ in ll]
        f = l[0]

        tmp = []
        for j in range(1, f+1):
            tmp.append(l[j])
        d += [tmp]

    mp = [[0 for i in range(30)] for j in range(n)]
    for member in range(n):
        for day in d[member]:
            mp[member][day] = 1
    clr = [0 for i in range(n)]
    ans = [1 for i in range(n)]
    flg = 0
    for day in range(30):
        tmp = []
        s = 0
        for member in range(n):
            s += mp[member][day]
            if mp[member][day] == 1:
                tmp.append(member)
        if s > 1:
            for member in tmp:
                clr[member] = 1
        if clr == ans and flg == 0:
            print(day)
            flg = 1

    if flg == 0:
        print(-1)

Submission status: Runtime Error

Solution code:
while(True):
    n = int(input())
    if n == 0:
        break
    d = []
    for i in range(n):
        ll = input().split()
        l = [int(_) for _ in ll]
        f = l[0]

        tmp = []
        for j in range(1, f+1):
            tmp.append(l[j])
        d += [tmp]

    mp = [[0 for i in range(30)] for j in range(n)]
    for member in range(n):
        for day in d[member]:
            mp[member][day] = 1
    clr = [0 for i in range(n)]
    ans = [1 for i in range(n)]
    flg = 0
    for day in range(30):
        tmp = []
        s = 0
        for member in range(n):
            s += mp[member][day]
            if mp[member][day] == 1:
                tmp.append(member)
        if s > 1:
            for member in tmp:
                clr[member] = 1
        if clr == ans and flg == 0:
            print(day)
            flg = 1

    if flg == 0:
        print(-1)

Submission status: Runtime Error

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  days = [[] for _ in range(30)]
  for i in range(n):
    hima = list(map(int, input().split()))
    for d in hima[1:]:
      days[d].append(i)

  par_lst = [i for i in range(n)]
  
  def get_par(x):
    if x == par_lst[x]:
      return x
    ret = get_par(par_lst[x])
    par_lst[x] = ret
    return ret

  for i, lst in enumerate(days, start=1):
    par = get_par(0)
    for i in range(n):
      if get_par(i) != par:
        break
    else:
      print(i)
      break

    if lst:
      par = get_par(lst[0])
      for num in lst:
        par_lst[get_par(num)] = par
  else:
    print(-1)