거위, 거위, 오리들?

첫 국제 거위 회의가 막 끝났지만, 행복한 자리였어야 했음에도 씁쓸한 결과를 맞았다. 주최 측이 오리들의 잠입에 관한 상세한 계획이 담긴 문서를 발견했다. 이제 주최 측은 참석자들 가운데 잠입한 무리를 식별하려 한다.

발견된 문서에는 정수 삼중항 $\mathbf{M}$개의 목록 $(\mathbf{X_i}, \mathbf{Y_i}, \mathbf{C_i})$이 들어 있었으며, 이는 오리들이 회의 시작 후 정확히 $\mathbf{C_i}$초에 회의장 중앙에서 동쪽으로 $\mathbf{X_i}$미터, 북쪽으로 $\mathbf{Y_i}$미터 떨어진 점 $(\mathbf{X_i}, \mathbf{Y_i})$에서 만난다는 뜻이다. 각 거위는 그 특정 시각에 그 특정 지점에 있었을 수도 있고 없었을 수도 있지만, 모든 오리는 분명히 그곳에 있었다.

오리와 거위는 모두 초당 최대 일 미터의 속도로 걷는다. 이는 시각 $t$에 점 $(x, y)$에 있는 참석자가 ${\Delta_{x}}^2 + {\Delta_{y}}^2 \le {\Delta_{t}}^2$인 한, 시각 $t + \Delta_{t}$까지 $(x + \Delta_{x}, y + \Delta_{y})$ 형태의 어떤 점에도 도달할 수 있다는 뜻이다. 시각 $0$에서 각 참석자의 위치는 다른 참석자들과 독립적으로 어떤 점이든 될 수 있다.

문서를 발견한 뒤, 이들은 오리를 식별하기 위해 심문 시간을 가졌다. 그 시간 동안 참석자들은 한 번에 하나씩 일련의 진술을 했다. 진술된 순서대로 그중 $j$번째 진술은 참석자 $\mathbf{A_j}$가 했으며, 자신과 참석자 $\mathbf{B_j}$가 회의 시작 후 정확히 $\mathbf{D_j}$초에 모두 점 $(\mathbf{U_j}, \mathbf{V_j})$에 있었다고 주장했다. 진술에 등장하는 점은 오리들의 만남이 있었던 점일 수도 있고 아닐 수도 있다.

거위의 진술은 항상 참이지만, 오리는 거짓말을 할 수도 있다. 또한 오리는 어떤 참석자가 오리이고 어떤 참석자가 거위인지 안다. 쉽게 들키지 않기 위해, 오리는 이전에 거위가 한 모든 진술과 모순되지 않는 진술만 한다. 거위가 한 진술은 모든 오리가 모든 오리 모임에 참석했다는 사실과 모순되지 않는다는 점에 유의하라.

주어진 정보로 모든 오리를 알아내는 것은 불가능할 수도 있다. 하지만 오리의 최소 수를 알면 적어도 오리 활동 수준의 하한을 구할 수 있다. 적어도 한 마리의 오리가 있었다는 점에 유의하라. 이 오리의 최소 수를 구하라.

형식적으로, 가설 $H$는 모든 참석자를 오리의 집합($H$-오리라고 부른다)과 거위의 집합($H$-거위라고 부른다)으로 분할한 것이다. 각 참석자에게 초당 최대 일 미터로 이동하는 경로가 존재하여 다음 조건을 만족할 때, 그리고 그럴 때에만 가설 $H$가 진술 집합 $S$와 모순되지 않는다.

• 모든 $H$-오리가 모든 오리 모임에 참석했고

• $A$가 시각 $T$에 점 $P$에서 $B$를 보았다고 주장하는 $S$의 각 진술에 대해, $A$와 $B$⁠의 경로가 모두 시각 $T$에 점 $P$을 지났다.

다음 조건을 만족할 때, 그리고 그럴 때에만 가설 $H$는 진술 집합 $S$ 아래에서 가능하다.

• $H$-오리가 공집합이 아니다(즉, 적어도 한 마리의 오리가 있었다).

• $H$-거위의 구성원들이 한 $S$의 모든 진술로 이루어진 부분집합이 $H$와 모순되지 않는다(즉, 거위의 진술은 항상 참이다).

• $H$-오리의 구성원이 한 각 진술 $s \in S$에 대해, $P \subseteq S$가 $s$보다 먼저 진술된 것들 중 $H$-거위의 구성원이 한 진술의 부분집합이라면, $\{ s \} \cup P$가 $H'$와 모순되지 않도록 하는 가설 $H'$가 존재한다. 이 가설은 $H$와 같을 수도 있고 다를 수도 있다(즉, 오리는 거위가 이전에 한 진술과 모순되는 말을 하지 않는다).

$H$-오리가 모든 참석자를 포함하는 가설 $H$는 항상 가능하다는 점에 유의하라.

가능한 모든 가설 $H$에 대해 $H$-오리 크기의 최솟값을 구하라.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 50$. 모든 $i$에 대해 $-10^9 \le \mathbf{X_i} \le 10^9$. 모든 $i$에 대해 $-10^9 \le \mathbf{Y_i} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{C_i} \le 10^9$. 모든 $i$에 대해 $\mathbf{C_i} \lt \mathbf{C_{i+1}}$. 모든 $i$에 대해 $(\mathbf{X_i} - \mathbf{X_{i+1}})^2 + (\mathbf{Y_i} - \mathbf{Y_{i+1}})^2 \le (\mathbf{C_i} - \mathbf{C_{i+1}})^2$. 모든 $j$에 대해 $1 \le \mathbf{A_j} \le \mathbf{N}$. 모든 $j$에 대해 $1 \le \mathbf{B_j} \le \mathbf{N}$. 모든 $j$에 대해 $\mathbf{A_j} \ne \mathbf{B_j}$. 모든 $j$에 대해 $-10^9 \le \mathbf{U_j} \le 10^9$. 모든 $j$에 대해 $-10^9 \le \mathbf{V_j} \le 10^9$. 모든 $j$에 대해 $1 \le \mathbf{D_j} \le 10^9$. 모든 $j \ne k$에 대해 $(\mathbf{A_j}, \mathbf{B_j}, \mathbf{U_j}, \mathbf{V_j}, \mathbf{D_j}) \ne (\mathbf{A_k}, \mathbf{B_k}, \mathbf{U_k}, \mathbf{V_k}, \mathbf{D_k})$.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $2 \le \mathbf{N} \le 50$. $1 \le \mathbf{M} \le 50$. $1 \le \mathbf{S} \le 50$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 60초. $2 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{M} \le 10^5$. $1 \le \mathbf{S} \le 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 참석자 수, 오리 모임 수, 진술 수를 각각 나타내는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{S}$이 포함된 줄로 시작한다. 다음 $\mathbf{M}$개의 줄은 각각 서로 다른 오리 모임 하나를 세 정수 $\mathbf{X_i}$, $\mathbf{Y_i}$, $\mathbf{C_i}$로 설명하며, 이는 회의 시작 후 정확히 $\mathbf{C_i}$초에 점 $(\mathbf{X_i}, \mathbf{Y_i})$에서 모임이 열렸음을 나타낸다. 그다음 테스트 케이스의 마지막 $\mathbf{S}$개의 줄은 각각 진술 하나를 설명한다. 이 중 $j$번째 줄은 $j$번째로 나온 진술을 다섯 정수 $\mathbf{A_j}$, $\mathbf{B_j}$, $\mathbf{U_j}$, $\mathbf{V_j}$, $\mathbf{D_j}$로 설명하며, 이는 참석자 $\mathbf{A_j}$가 자신과 참석자 $\mathbf{B_j}$가 회의 시작 후 정확히 $\mathbf{D_j}$초에 모두 점 $(\mathbf{U_j}, \mathbf{V_j})$에 있었다고 진술했음을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 1부터 시작하는 테스트 케이스 번호이고, $y$는 회의에 잠입했을 가능성이 있는 오리의 최소 수이다.

예제 케이스 #1에서는 참석자 1만 오리라는 가설이 가능하다.

예제 케이스 #2에서는 참석자 2과 4만 오리라는 가설이 가능하다. 적어도 한 마리의 오리가 있으므로 모든 참석자가 거위라는 가설은 가능하지 않다는 점에 유의하라.