1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| #pragma comment(linker, "/STACK:16777216")
#include <bits/stdc++.h>
using namespace std;
#define IO_SIZE 1048576
char buf[IO_SIZE], *S, *T, IO_c, IO_signum;
inline char read() {
if (S == T) {
T = (S = buf) + fread(buf, 1, IO_SIZE, stdin);
if (S == T) return EOF;
}
return *S++;
}
inline bool read(int& x) {
IO_signum = false;
for (IO_c = read(); IO_c < '0' || IO_c > '9'; IO_c = read()) {
if (IO_c == -1) return false;
if (IO_c == '-') IO_signum = true;
}
x = 0;
while (IO_c == 0) IO_c = read();
for (;; IO_c = read()) {
if (IO_c < '0' || IO_c > '9') break;
x = (x << 3) + (x << 1) + (IO_c ^ '0');
}
}
#define in(x, y) read(x), read(y)
int n, m, q;
struct node {
int to, next, w;
} edge[100010];
int disJointRank[50010], father[50010];
#define makeSet(x) disJointRank[x] = 0, father[x] = x;
inline int getFather(int x) {
register int px = x, i;
while (px ^ father[px]) px = father[px];
while (x ^ px) i = father[x], father[x] = px, x = i;
return px;
}
inline void unionSet(int x, int y) {
x = getFather(x), y = getFather(y);
if (disJointRank[x] > disJointRank[y])
father[y] = x;
else {
father[x] = y;
if (disJointRank[x] == disJointRank[y]) disJointRank[y]++;
}
}
inline int gcd(int x, int y) {
register int i, j;
if (!x) return y;
if (!y) return x;
for (i = 0; 0 == (x & 1); ++i) x >>= 1;
for (j = 0; 0 == (y & 1); ++j) y >>= 1;
if (j < i) i = j;
while (true) {
if (x < y) x ^= y ^= x ^= y;
if (!(x -= y)) return y << i;
while (!(x & 1)) x >>= 1;
}
}
#define insert(u, v, w) \
edge[++size].to = v, edge[size].w = w, edge[size].next = first[u], \
first[u] = size
int ans[50010], first[50010], size, color[50010];
bool vis[50010], flag;
inline void dfs1(int now) {
color[now] = -1;
for (register int u = first[now]; u; u = edge[u].next) {
ans[father[now]] = gcd(ans[father[now]], edge[u].w);
if (color[edge[u].to] ^ -1) dfs1(edge[u].to);
}
}
inline void dfs2(int now) {
vis[now] = true;
for (register int u = first[now]; u; u = edge[u].next) {
ans[father[now]] = gcd(ans[father[now]], edge[u].w);
if (!vis[edge[u].to]) dfs2(edge[u].to);
}
}
inline void dfs(int now, int column = 1) {
color[now] = column;
for (register int u = first[now]; u; u = edge[u].next) {
if (color[edge[u].to]) {
if ((edge[u].w / ans[father[now]]) & 1) {
if (color[edge[u].to] == color[now]) {
flag = true;
return;
}
} else {
if (color[edge[u].to] ^ color[now]) {
flag = true;
return;
}
}
} else {
if ((edge[u].w / ans[father[now]]) & 1)
dfs(edge[u].to, (((column - 1) ^ 1) + 1));
else
dfs(edge[u].to, column);
if (flag) return;
}
}
}
int main() {
freopen("pod.in", "r", stdin);
freopen("pod.out", "w", stdout);
in(n, m), read(q);
for (register int i = 1; i <= n; ++i) father[i] = i;
for (register int i = 1, u, v, w; i <= m; ++i)
in(u, v), read(w), insert(u, v, w), insert(v, u, w), unionSet(u, v);
for (register int i = 1; i <= n; ++i) getFather(i);
for (register int i = 1; i <= n; ++i)
if (father[i] == i) ans[i] = edge[first[i]].w;
for (register int i = 1; i <= n; ++i) {
if (!color[i]) dfs2(i), dfs(i);
if (flag) dfs1(i), flag = false;
}
for (register int i = 1, u, v, w; i <= q; ++i) {
in(u, v), read(w);
if (getFather(u) ^ getFather(v)) {
cout << "NIE\n";
continue;
}
if ((w / gcd(w, ans[father[u]]) & 1) || (color[u] == color[v])) {
cout << "0\n";
continue;
} else
cout << gcd(w, ans[father[u]]) << "\n";
}
return 0;
}
|
