fork download
copy 
  1. #include <cstdio>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <memory.h>
  6. #include <cmath>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <stack>
  11. #include <ctime>
  12. #include <iostream>
  13. #include <functional>
  14. #include <complex>
  15. #include <stdlib.h>
  16. #include <fstream>
  17. #include <random>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22. typedef pair<int, int> pii;
  23. typedef pair<double, double> pdd;
  24. typedef pair<pii, int> p3i;
  25. typedef vector<int> vi;
  26. typedef vector<pii> vii;
  27. typedef vector<p3i> v3i;
  28. typedef vector<vii> vvii;
  29. typedef vector<p3i> vp3i;
  30. typedef long double ld;
  31. typedef vector<ld> vld;
  32.  
  33. #define pb push_back
  34. #define mp make_pair
  35. #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
  36. #define REPD(i, n) for (int (i) = (n) - 1; (i) >= 0; (i)--)
  37. #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
  38. #define FORD(i,a, b) for (int (i) = (a); (i) >= (b); (i)--)
  39. #define sz(v) (int)(v).size()
  40. #define all(v) (v).begin(), (v).end()
  41. #define rv(v) reverse(all(v))
  42. #define CL(v, val) memset((v), (val), sizeof((v)))
  43. #define SORT(a) sort(all(a))
  44. #define un(v) SORT(v), (v).resize(unique(all(v)) - (v).begin())
  45. #define eps 1.0e-9
  46. #define X first
  47. #define Y second
  48. #define bit(n) (1 << (n))
  49. #define bit64(n) (ll(1) << (n))
  50. #define sqr(x) ((x) * (x))
  51. #define sq5(x) ((x) * (x) * (x) * (x) * (x))
  52.  
  53. vi p, l, r;
  54. vector<bool> used;
  55. int tmp[4];
  56.  
  57. vector<vi> g;
  58. queue<int> q,q1;
  59.  
  60. bool bfs(int v) {
  61. 	if (used[v]) {
  62. 		return 1;
  63. 	}
  64.  
  65. 	q.push(v);
  66.  
  67. 	while (sz(q)) {
  68. 		int u = q.front();
  69. 		q.pop();
  70.  
  71. 		if (sz(g[u]) == 3) {
  72. 			tmp[3] = u;
  73. 			REP(i, 3) {
  74. 				tmp[i] = g[u][i];
  75. 			}
  76.  
  77. 			sort(tmp, tmp + 4);
  78.  
  79. 			if (tmp[1] == u) {
  80. 				if (p[u] != -1 && p[u] != tmp[3]) {
  81. 					return 0;
  82. 				}
  83. 				p[u] = tmp[3];
  84. 				if (l[tmp[3]] != -1 && l[tmp[3]] != u) {
  85. 					return 0;
  86. 				}
  87. 				l[tmp[3]] = u;
  88. 				if (l[u] != -1 && l[u] != tmp[0]) {
  89. 					return 0;
  90. 				}
  91. 				l[u] = tmp[0];
  92. 				if (p[tmp[0]] != -1 && p[tmp[0]] != u) {
  93. 					return 0;
  94. 				}
  95. 				p[tmp[0]] = u;
  96. 				if (r[u] != -1 && r[u] != tmp[2]) {
  97. 					return 0;
  98. 				}
  99. 				r[u] = tmp[2];
  100. 				if (p[tmp[2]] != -1 && p[tmp[2]] != u) {
  101. 					return 0;
  102. 				}
  103. 				p[tmp[2]] = u;
  104. 				if (!used[tmp[0]]) {
  105. 					q.push(tmp[0]);
  106. 					used[tmp[0]] = 1;
  107. 				}
  108. 				if (!used[tmp[2]]) {
  109. 					used[tmp[2]] = 1;
  110. 					q.push(tmp[2]);
  111. 				}
  112. 				if (!used[tmp[3]]) {
  113. 					used[tmp[3]] = 1;
  114. 					q.push(tmp[3]);
  115. 				}
  116. 			}
  117.  
  118. 			if (tmp[2] == u) {
  119. 				if (p[u] != -1 && p[u] != tmp[0]) {
  120. 					return 0;
  121. 				}
  122. 				p[u] = tmp[0];
  123. 				if (r[tmp[0]] != -1 && r[tmp[0]] != u) {
  124. 					return 0;
  125. 				}
  126. 				r[tmp[0]] = u;
  127. 				if (l[u] != -1 && l[u] != tmp[1]) {
  128. 					return 0;
  129. 				}
  130. 				l[u] = tmp[1];
  131. 				if (p[tmp[1]] != -1 && p[tmp[1]] != u) {
  132. 					return 0;
  133. 				}
  134. 				p[tmp[1]] = u;
  135. 				if (r[u] != -1 && r[u] != tmp[3]) {
  136. 					return 0;
  137. 				}
  138. 				r[u] = tmp[3];
  139. 				if (p[tmp[3]] != -1 && p[tmp[3]] != u) {
  140. 					return 0;
  141. 				}
  142. 				p[tmp[3]] = u;
  143. 				if (!used[tmp[0]]) {
  144. 					used[tmp[0]] = 1;
  145. 					q.push(tmp[0]);
  146. 				}
  147. 				if (!used[tmp[1]]) {
  148. 					used[tmp[1]] = 1;
  149. 					q.push(tmp[1]);
  150. 				}
  151. 				if (!used[tmp[2]]) {
  152. 					used[tmp[2]] = 1;
  153. 					q.push(tmp[2]);
  154. 				}
  155. 			}
  156. 		}
  157.  
  158. 		if (sz(g[u]) == 2) {
  159. 			tmp[2] = u;
  160. 			REP(i, 2) {
  161. 				tmp[i] = g[u][i];
  162. 			}
  163.  
  164. 			sort(tmp, tmp + 3);
  165.  
  166. 			if (tmp[0] == u) {
  167. 				if (p[u] != -1 && p[u] != tmp[2]) {
  168. 					return 0;
  169. 				}
  170. 				p[u] = tmp[2];
  171. 				if (l[tmp[2]] != -1 && l[tmp[2]] != u) {
  172. 					return 0;
  173. 				}
  174. 				l[tmp[2]] = u;
  175. 				if (r[u] != -1 && r[u] != tmp[1]) {
  176. 					return 0;
  177. 				}
  178. 				r[u] = tmp[1];
  179. 				if (p[tmp[1]] != -1 && p[tmp[1]] != u) {
  180. 					return 0;
  181. 				}
  182. 				p[tmp[1]] = u;
  183. 				if (!used[tmp[1]]) {
  184. 					used[tmp[1]] = 1;
  185. 					q.push(tmp[1]);
  186. 				}
  187. 				if (!used[tmp[2]]) {
  188. 					used[tmp[2]] = 1;
  189. 					q.push(tmp[2]);
  190. 				}
  191. 			}
  192.  
  193. 			if (tmp[2] == u) {
  194. 				if (p[u] != -1 && p[u] != tmp[0]) {
  195. 					return 0;
  196. 				}
  197. 				p[u] = tmp[0];
  198. 				if (r[tmp[0]] != -1 && r[tmp[0]] != u) {
  199. 					return 0;
  200. 				}
  201. 				r[tmp[0]] = u;
  202. 				if (l[u] != -1 && l[u] != tmp[1]) {
  203. 					return 0;
  204. 				}
  205. 				l[u] = tmp[1];
  206. 				if (p[tmp[1]] != -1 && p[tmp[1]] != u) {
  207. 					return 0;
  208. 				}
  209. 				p[tmp[1]] = u;
  210. 				if (!used[tmp[0]]) {
  211. 					used[tmp[0]] = 1;
  212. 					q.push(tmp[0]);
  213. 				}
  214. 				if (!used[tmp[1]]) {
  215. 					used[tmp[1]] = 1;
  216. 					q.push(tmp[1]);
  217. 				}
  218. 			}
  219.  
  220. 			if (tmp[1] == u) {
  221. 				if (p[u] == tmp[0]) {
  222. 					if (r[u] != -1 && r[u] != tmp[2]) {
  223. 						return 0;
  224. 					}
  225. 					r[u] = tmp[2];
  226. 					if (p[tmp[2]] != -1 && p[tmp[2]] != u) {
  227. 						return 0;
  228. 					}
  229. 					p[tmp[2]] = u;
  230. 					if (!used[tmp[2]]) {
  231. 						used[tmp[2]] = 1;
  232. 						q.push(tmp[2]);
  233. 					}
  234. 				}
  235.  
  236. 				if (p[u] == tmp[2]) {
  237. 					if (l[u] != -1 && l[u] != tmp[0]) {
  238. 						return 0;
  239. 					}
  240. 					l[u] = tmp[0];
  241. 					if (p[tmp[0]] != -1 && p[tmp[0]] != u) {
  242. 						return 0;
  243. 					}
  244. 					p[tmp[0]] = u;
  245. 					if (!used[tmp[0]]) {
  246. 						used[tmp[0]] = 1;
  247. 						q.push(tmp[0]);
  248. 					}
  249. 				}
  250. 			}
  251. 		}
  252. 	}
  253.  
  254. 	return 1;
  255. }
  256.  
  257. vi order;
  258.  
  259. void InOrder(int v) {
  260. 	stack<int> st;
  261.  
  262. 	while (true) {
  263.  
  264. 		while (v != -1) {
  265. 			st.push(v);
  266. 			v = l[v];
  267. 		}
  268.  
  269. 		if (v == -1 && sz(st)) {
  270. 			int top = st.top();
  271. 			st.pop();
  272. 			order.pb(top);
  273. 			v = r[top];
  274. 		}
  275.  
  276. 		if (v == -1 && sz(st) == 0) {
  277. 			break;
  278. 		}
  279. 	}
  280.  
  281.  
  282.  
  283. }
  284.  
  285. int main(void) {
  286. 	int n;
  287. 	scanf("%d", &n);
  288. 	g.resize(n);
  289. 	p.resize(n, -1);
  290. 	l.resize(n, -1);
  291. 	r.resize(n, -1);
  292. 	used.resize(n, 0);
  293.  
  294. 	REP(i, n - 1) {
  295. 		int x, y;
  296. 		scanf("%d%d", &x, &y);
  297. 		x--, y--;
  298. 		g[x].pb(y);
  299. 		g[y].pb(x);
  300. 	}
  301.  
  302.  
  303. 	REP(i, n) {
  304. 		if (sz(g[i]) == 3) {
  305. 			tmp[3] = i;
  306. 			REP(j, 3) {
  307. 				tmp[j] = g[i][j];
  308. 			}
  309.  
  310. 			sort(tmp, tmp + 4);
  311. 			if (tmp[0] == i || tmp[3] == i) {
  312. 				printf("-1\n");
  313. 				return 0;
  314. 			}
  315.  
  316. 			q1.push(i);
  317. 		}
  318.  
  319. 		if (sz(g[i]) == 2) {
  320. 			tmp[2] = i;
  321. 			REP(j, 2) {
  322. 				tmp[j] = g[i][j];
  323. 			}
  324.  
  325. 			sort(tmp, tmp + 3);
  326. 			if (tmp[0] == i || tmp[2] == i) {
  327. 				q1.push(i);
  328. 			}
  329. 		}
  330. 	}
  331.  
  332. 	while (sz(q1)) {
  333. 		bool ok = bfs(q1.front());
  334. 		if (!ok) {
  335. 			printf("-1\n");
  336. 			return 0;
  337. 		}
  338. 		q1.pop();
  339. 	}
  340.  
  341. 	int p1 = -1, p2 = -1;
  342. 	REP(i, n) {
  343. 		if (p[i] == -1) {
  344. 			if (p1 == -1) {
  345. 				p1 = i;
  346. 			}
  347. 			p2 = i;
  348. 		}
  349. 	}
  350.  
  351. 	bool ok = 1;
  352. 	if (p2 - p1 > 1) {
  353. 		FOR(i, p1, p2) {
  354. 			r[i] = i + 1;
  355. 			p[i + 1] = i;
  356. 		}
  357. 	}
  358.  
  359. 	InOrder(p1);
  360. 	REP(i, sz(order)) {
  361. 		if (order[i] != i ) {
  362. 			printf("-1\n");
  363. 			return 0;
  364. 		}
  365. 	}
  366.  
  367. 	if (ok) {
  368. 		FOR(i, p1, p2 + 1) {
  369. 			printf("%d%c", i + 1, " \n"[i == p2]);
  370. 		}
  371. 	}
  372. }
  373.  
  374. /*
  375.  
  376. 16
  377. 1 2
  378. 2 3
  379. 2 4
  380. 4 5
  381. 5 6
  382. 6 11
  383. 11 10
  384. 10 9
  385. 9 8
  386. 8 7
  387. 11 16
  388. 16 12
  389. 12 14
  390. 14 13
  391. 14 15
  392.  
  393. */
Runtime error #stdin #stdout 0s 4956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0veMsS
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!