Wrong Answer

Time limit1sMemory limit256 MB

Summary

Given horizontal and vertical words, remove the fewest words so no horizontal and vertical word demand different letters at a shared cell.

Level: Medium7 of 10
Topics: Graph, Union-find, Binary search, Greedy
Solved: No attempts yet

Problem

Seunghyuk is solving a crossword puzzle. At each fixed position on the board he wants to write one word, either horizontally or vertically. However, when a horizontal word and a vertical word pass through the same cell, they conflict if they require different letters in that cell.

Without changing any of the words, Seunghyuk wants to choose a subset of the words and place them so that no two chosen words conflict. Find the maximum number of words he can place.

Words of the same orientation (horizontal with horizontal, vertical with vertical) never overlap, so they never conflict. A conflict occurs only when a horizontal word and a vertical word meet at a single cell and demand different letters there.

Input

The first line contains the number of test cases $T$ . Each test case is given as follows.

The first line contains two integers $H$ and $V$ , the number of horizontal words and the number of vertical words. ( $1 \le H, V \le 500$ )
Each of the next $H$ lines contains the starting-cell coordinates $x$ , $y$ and the word $W$ of one horizontal word. ( $0 \le x, y \le 1000$ , $1 \le |W| \le 1000$ )
Each of the next $V$ lines contains the starting-cell coordinates $x$ , $y$ and the word $W$ of one vertical word. ( $0 \le x, y \le 1000$ , $1 \le |W| \le 1000$ )

Every word consists of uppercase English letters only. No two horizontal words overlap, and no two vertical words overlap.

The top-left cell of the board has coordinates $x = y = 0$ . Here $x$ is the horizontal (column) position and $y$ is the vertical (row) position. A horizontal word is written from its starting cell to the right (increasing $x$ ), and a vertical word is written from its starting cell downward (increasing $y$ ). Thus the $k$ -th letter of a horizontal word starting at $(x, y)$ occupies cell $(x+k, y)$ , and the $k$ -th letter of a vertical word occupies cell $(x, y+k)$ (where $k$ starts from 0).

Output

For each test case, print on a single line the maximum number of words that can be placed so that no two of them conflict.

Examples3

Example 1

Input

2
2 2
0 1 BAPC
0 2 LEIDEN
0 0 SOLUTION
2 1 WINNER
1 4
0 1 HELLO
1 0 HI
2 0 BYE
3 0 GOODBYE
4 0 FAREWELL

Expected output

3
4

Example 2
Input
```
1
1 1
0 0 A
0 0 B
```
Expected output
```
1
```
Example 3
Input
```
1
1 1
0 0 AB
0 0 AC
```
Expected output
```
2
```