Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- //#define endl '\n'
- #define boostIO() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
- int n;
- vector <multiset<int>> g;
- vector<int> path(int v) {
- stack<int> s;
- vector<int> ans;
- s.push(v);
- while (!s.empty()) {
- int w = s.top();
- bool found_edge = false;
- for (int u = 0; u < n; ++u) {
- if (g[w].count(u)) {
- s.push(u);
- g[w].erase(g[w].find(u));
- found_edge = true;
- break;
- }
- }
- if (!found_edge) {
- s.pop();
- ans.push_back(w);
- }
- }
- return ans;
- }
- signed main() {
- int start;
- cin >> n >> start;
- --start;
- g.resize(n);
- vector<map<int, vector<int>>> q(n);
- vector<vector<int>> e(n, vector<int>(3));
- for (int i = 0; i < n; ++i) {
- int a, b, c;
- cin >> a >> b >> c;
- --a, --b;
- e[i] = { a, b, c };
- if (c == 1) {
- g[a].insert(b);
- q[a][b].push_back(i);
- }
- }
- auto p = path(start);
- reverse(all(p));
- vector<int> ans1, ans;
- //for (auto& x : p) cout << x + 1 << " ";
- for (int i = 0; i < p.size() - 1; ++i) {
- if (q[p[i]][p[i + 1]].size() == 0) {
- cout << "No";
- return 0;
- }
- ans1.push_back(q[p[i]][p[i + 1]].back());
- q[p[i]][p[i + 1]].pop_back();
- }
- for (int i = 0; i < e.size(); ++i) {
- if (e[i][2] == 0 && e[i][0] != start) ans.push_back(i);
- }
- if (ans1.size()) ans.push_back(ans1[0]);
- for (int i = 0; i < e.size(); ++i) {
- if (e[i][2] == 0 && e[i][0] == start) ans.push_back(i);
- }
- for (int i = 1; i < ans1.size(); ++i) {
- ans.push_back(ans1[i]);
- }
- if (ans.size() != n) {
- cout << "No";
- return 0;
- }
- for (int i = 0; i < n; ++i) {
- auto& cur = e[ans[i]];
- if (cur[2] == 0) {
- if (start != cur[0]) continue;
- cout << "No";
- return 0;
- }
- else {
- if (start != cur[0]) {
- cout << "No";
- return 0;
- }
- start = cur[1];
- }
- }
- cout << "Yes\n";
- for (auto& x : ans) cout << x + 1 << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement