1854 - 比大小 V2
Description

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

1\leq n \leq 1000,1\leq m \leq n \times 10,1\leq q \leq n\times (n-1)\div 2

例如共 5 个变量 v_1v_5v_1>v_2v_2>v_3v_2>v_5v_5<v_3v_4>v_3

询问 v_1v_4 的关系,由于 v_1>v_2,v_2>v_3,v_4>v_3 ,这些比较并不能确定 v_1v_4 之间的关系,所以结果为 unknown 。

询问 v_1v_5 的关系,由于 v_1>v_2,v_2>v_3,v_5<v_3 。所以 v_1 一定大于 v_5


Input

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

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

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

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

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


Output

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

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


Examples

Input

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

Output

0
1
2
Hint

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

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

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


题目参数
Time Limit 1 second
Memory Limit 256 MB
提交次数 67
通过次数 19