만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

거위, 거위, 오리?

메모리 제한1024 MB

요약
오리 모임 기록과 진술이 주어졌을 때, 거위 진술이 모두 맞고 오리 진술이 앞선 거위 진술과 어긋나지 않는 조건에서 오리의 최소 인원을 구합니다.
난이도

어려움10점 중 9점

유형
그래프, 유니온 파인드, 구현
정답자
아직 제출이 없습니다

문제

처음 열린 국제 거위 학회가 막 끝났다. 행사는 기쁜 자리였어야 했지만 씁쓸하게 마무리되었다. 주최 측이 오리의 잠입 계획이 자세히 적힌 문서를 발견했고, 지금은 참석자 중에서 잠입한 무리를 찾고 있다.

문서에는 정수 세 개로 이루어진 순서쌍 (Xi,Yi,Ci)(X_i, Y_i, C_i)가 MM개 적혀 있었다. 이 순서쌍은 학회 시작 후 정확히 CiC_i초에 오리들이 좌표 (Xi,Yi)(X_i, Y_i)에서 만날 예정이었다는 뜻이다. 좌표 (X,Y)(X, Y)는 학회장 중앙에서 동쪽으로 XX미터, 북쪽으로 YY미터 떨어진 지점이다. 거위는 그 시각에 그 지점에 있었을 수도, 없었을 수도 있다. 그러나 모든 오리는 반드시 그곳에 있었다.

오리와 거위는 최대 초속 1미터로 걷는다. 따라서 시각 tt에 (x,y)(x, y)에 있는 참석자는 Δx2+Δy2≤Δt2\Delta_x^2+\Delta_y^2 \le \Delta_t^2만 만족하면 시각 t+Δtt+\Delta_t에 (x+Δx,y+Δy)(x+\Delta_x, y+\Delta_y)에 도달할 수 있다. 시각 0에서 각 참석자의 위치는 어느 점이든 될 수 있으며, 다른 참석자와 무관하다.

발견 이후 모임은 오리를 가려내기 위해 질의 세션을 열었다. 세션에서 참석자들은 진술을 한 번에 하나씩 했다. jj번째 진술은 참석자 AjA_j가 했으며, 자신과 참석자 BjB_j가 학회 시작 후 정확히 DjD_j초에 좌표 (Uj,Vj)(U_j, V_j)에 있었다고 주장한다. 진술에 나온 좌표는 오리 만남이 있었던 곳일 수도, 아닐 수도 있다.

거위의 진술은 항상 참이다. 오리는 거짓말을 할 수 있다. 오리는 누가 오리이고 누가 거위인지 알고 있다. 들키지 않으려고 오리는 앞서 나온 거위의 진술과 모순되지 않는 진술만 한다. 거위의 진술은 모든 오리가 모든 오리 만남에 있었다는 사실과 일관된다는 점에 유의하라.

가설 HH는 참석자 전체를 오리 집합(HH-오리)과 거위 집합(HH-거위)으로 나눈 분할이다. HH가 진술 집합 SS와 일관된다는 것은, 참석자마다 초당 1미터 이하로 움직이는 경로가 존재해서 다음이 성립한다는 뜻이다.

  • 모든 HH-오리가 모든 오리 만남에 있었다.
  • SS의 각 진술에서 AA가 시각 TT에 점 PP에서 BB를 만났다고 주장하면, AA와 BB의 경로가 모두 시각 TT에 점 PP를 지났다.

가설 HH가 진술 집합 SS 아래에서 실행 가능하다는 것은 다음 조건을 모두 만족한다는 뜻이다.

  • HH-오리 집합이 비어 있지 않다. 즉 오리가 적어도 한 마리 있다.
  • HH-거위가 한 진술 전체는 HH와 일관된다. 즉 거위의 진술은 모두 참이다.
  • HH-오리가 한 SS의 각 진술 ss에 대해, ss 이전에 나온 HH-거위의 진술 집합을 PP라 하자. 그러면 {s}∪P\{s\} \cup P가 어떤 가설 H′H'와 일관되도록 하는 H′H'가 존재한다. H′H'는 HH와 같을 수도 다를 수도 있다. 즉 오리는 앞선 거위의 진술과 모순되지 않는다.

모든 참석자가 오리인 가설은 항상 실행 가능하다.

실행 가능한 모든 가설 HH에 대해 HH-오리 집합 크기의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스 수 TT가 주어진다. 각 테스트 케이스의 첫 줄에는 참석자 수 NN, 오리 만남 수 MM, 진술 수 SS를 나타내는 정수 세 개가 주어진다.

다음 MM개 줄에는 각각 정수 XiX_i, YiY_i, CiC_i가 주어진다. 이는 학회 시작 후 정확히 CiC_i초에 점 (Xi,Yi)(X_i, Y_i)에서 오리 만남이 있었다는 뜻이다.

이어서 마지막 SS개 줄에는 진술이 주어진다. jj번째 줄은 정수 다섯 개 AjA_j, BjB_j, UjU_j, VjV_j, DjD_j로 이루어지며, 참석자 AjA_j가 자신과 BjB_j가 학회 시작 후 정확히 DjD_j초에 점 (Uj,Vj)(U_j, V_j)에 있었다고 진술했다는 뜻이다. 진술은 발언된 순서대로 주어진다.

출력

각 테스트 케이스에 대해 Case #x: y 형식으로 한 줄을 출력한다. 여기서 xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 회의장에 잠입했을 수 있는 오리의 최소 마리 수이다.

제한

  • 1≤T≤501 \le T \le 50
  • 모든 ii에 대해 −109≤Xi≤109-10^9 \le X_i \le 10^9
  • 모든 ii에 대해 −109≤Yi≤109-10^9 \le Y_i \le 10^9
  • 모든 ii에 대해 1≤Ci≤1091 \le C_i \le 10^9
  • 모든 ii에 대해 Ci<Ci+1C_i < C_{i+1}
  • 모든 ii에 대해 (Xi−Xi+1)2+(Yi−Yi+1)2≤(Ci−Ci+1)2(X_i - X_{i+1})^2 + (Y_i - Y_{i+1})^2 \le (C_i - C_{i+1})^2
  • 모든 jj에 대해 1≤Aj≤N1 \le A_j \le N
  • 모든 jj에 대해 1≤Bj≤N1 \le B_j \le N
  • 모든 jj에 대해 Aj≠BjA_j \ne B_j
  • 모든 jj에 대해 −109≤Uj≤109-10^9 \le U_j \le 10^9
  • 모든 jj에 대해 −109≤Vj≤109-10^9 \le V_j \le 10^9
  • 모든 jj에 대해 1≤Dj≤1091 \le D_j \le 10^9
  • j≠kj \ne k인 모든 j,kj, k에 대해 (Aj,Bj,Uj,Vj,Dj)≠(Ak,Bk,Uk,Vk,Dk)(A_j, B_j, U_j, V_j, D_j) \ne (A_k, B_k, U_k, V_k, D_k)

힌트

예제 1에서는 참석자 1만 오리인 가설이 실행 가능하다.

예제 2에서는 참석자 2와 4만 오리인 가설이 실행 가능하다. 오리가 적어도 한 마리 있으므로 모든 참석자가 거위인 가설은 실행 가능하지 않다.

예제1

  1. 예제 1

    입력
    2
2 1 2
1 2 3
1 2 1 1 1
2 1 2 2 2
4 2 4
4 3 10
-4 -3 20
1 3 4 3 11
2 4 0 0 16
3 1 6 3 9
4 2 0 0 16
    예상 출력
    Case #1: 1
Case #2: 2