Inference

Given $m$ features, you want to infer the last feature's value of Alice by the value of her first $m-1$ features, based on massive data.

The relationship between features can be represented as a directed acyclic graph, where a node $A$ pointing to a node $B$ indicates that $B$ is a random variable dependent on $A$.

The following formula can calculate the probability of the last feature's value of Alice based on other data, in which $x_i$ represents the $i-$th feature, $\pi(x_i)$ represents nodes that point to $x_i$, and $cnt$ represents their number of occurrences:
$$P(x_m|x_1,\dots,x_{m-1})=cP(x_1,\dots,x_m)=\prod_{i=1}^m P(x_i|\pi(x_i))$$

$$P(x_i|\pi(x_i))=\frac{P(\pi(x_i), x_i)}{P(\pi(x_i))}=\begin{cases}\frac{cnt(\pi(x_i), x_i)}{cnt(\pi(x_i))},\text{ if }cnt(\pi(x_i))\ne 0\\\\0,\text{ if }cnt(\pi(x_i))=0\end{cases}$$

It is guaranteed that the last feature has zero out-degree, and there exists at least one case of value such that $cnt(\pi(x_i))\ne0$.

Now, given $n$ people's data, what is the most likely value of the $m-$th feature of Alice, given the value of her first $m-1$ features.

At the beginning of the input section, there is an integer $T(1\le T\le 10)$, indicating the number of test cases.

For every test case, the first line consists of three integers $n(1\le n\le 10^4)$, $m(1\le m\le 100)$, $k(1\le k\le 300)$, indicating the number of data, the number of features, and the number of the relationship between the features.

In the next $k$ rows, each row contains two integers $x,y(1\le x,y \le m)$, indicating node $x$ point to node $y$, thus $y-$th feature is dependent on $x-$th feature. Every point has an in-degree less than 5.

In the next $n$ rows, each row contains $m$ integers indicating one person's values of each feature. Every feature's value is among $0,1,2$.

In the last line, there are $m-1$ integers indicating Alice's values of the first $m-1$ features.

(请不要使用 scanf 进行读入)

An integer denoting the most probable value of Alice's $m-$th feature.

It is guaranteed that there exists only $1$ value which has the biggest probability.

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

0

In the example, there are $10$ people's data, $5$ features, and $4$ edges between the features. The table of data is shown in the following table.

| Effort | Weather | Appetite | Grade | Personality |
| ------ | ------- | -------- | ----- | ----------- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | ? |

The relation between features is shown in the following graph.

<img src="https://img1.imgtp.com/2023/08/13/O99LVJ57.png" alt="示例" style="zoom: 50%;" />

To calculate the possibility that the $5$-th feature has a value $0$ in the last line of data, we use the formula:

$$P(x_m|x_1,\dots,x_{m-1})=cP(x_1,\dots,x_m)=\prod_{i=1}^m P(x_i|\pi(x_i))$$
$$=P(x_1=1)\cdot P(x_2=1)\cdot P(x_3=0)\cdot P(x_4=0|x_1=1,x_2=1)\cdot P(x_5=0|x_3=0,x_4=0)$$
$$=\frac{5}{10}\cdot\frac{6}{10}\cdot\frac{5}{10}\cdot\frac{1}{3}\cdot\frac{1}{1}=0.05$$

The possibility that the $5-$th feature has a value $1$ or $2$ is $0$, which is less than $0.05$. So we take $0$ as the value of $5$-th feature.

2023“钉耙编程”中国大学生算法设计超级联赛（9）