1854 - 比大小 V2
描述

有 n 个互不相等的变量 v1 到 vn ,不知道每个变量的具体值。但有  m 个变量间的比较关系。例如: v1>v2,v3<v2 。有 q 组询问,每次询问 2 个变量之间的大小关系。结果有 3 种可能,> < unknown 。

( 1≤n≤1000 , 1≤m≤n×10 , 1≤q≤n×(n−1)/2 ;)

例如共 5 个变量 v1 到 v5 :v1>v2 , v2>v3 , v2>v5 , v5<v3 , v4>v3 。

询问 v1 和 v4 的关系,由于 v1>v2,v2>v3,v4>v3 ,这些比较并不能确定 v1 同 v4 之间的关系,所以结果为 unknown 。

询问 v1 和 v5 的关系,由于 v1>v2,v2>v3,v5<v3 。所以 v1 一定大于 v5 。


输入

第一行,输入三个数字 n , m 和 q ,表示变量的个数和关系的个数以及询问的个数;

接下来 m 行,每行三个数, flag,a,b ;

当 flag=1 的时候,表示 a>b; 

当 flag=2 的时候,表示 a<b 。

接下来 q 行,每行两个数字 x 和 y ,表示询问 x 和 y 的大小关系;


输出

输出包括 q 行,每行一个数表示一个判断结果;

当 x>y 时输出 1 ,当 x<y 时输出 2 ,无法判断 x 和 y 的关系时(即 unknown )输出 0 。


样例

输入

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

输出

0
1
2
提示

对于 10% 的数据, 1≤n≤4 ;

对于 50% 的数据, 1≤n≤500 ;

对于 100% 的数据, 1≤n≤1000 ; 1≤m≤n×10 , 1≤q≤n×(n−1)/2 ;


题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 20
通过次数 6