//#pragma GCC optimize("Ofast") //#pragma GCC target("avx") //#undef LOCAL #include #include #include #include #include #include #include #include #include #include namespace yosupo { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } } // namespace internal int bsf(unsigned int n) { return __builtin_ctz(n); } int bsf(unsigned long n) { return __builtin_ctzl(n); } int bsf(unsigned long long n) { return __builtin_ctzll(n); } int bsf(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return low ? __builtin_ctzll(low) : 64 + __builtin_ctzll(high); } int bsr(unsigned int n) { return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n); } int bsr(unsigned long n) { return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n); } int bsr(unsigned long long n) { return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n); } int bsr(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low); } int popcnt(unsigned int n) { return __builtin_popcount(n); } int popcnt(unsigned long n) { return __builtin_popcountl(n); } int popcnt(unsigned long long n) { return __builtin_popcountll(n); } } // namespace yosupo #include #include #include namespace yosupo { namespace internal { template using is_signed_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using is_integral = typename std::conditional::value || internal::is_signed_int128::value || internal::is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed_int = typename std::conditional<(is_integral::value && std::is_signed::value) || is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned_int = typename std::conditional<(is_integral::value && std::is_unsigned::value) || is_unsigned_int128::value, std::true_type, std::false_type>::type; template using to_unsigned = typename std::conditional< is_signed_int128::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; template using is_integral_t = std::enable_if_t::value>; template using is_signed_int_t = std::enable_if_t::value>; template using is_unsigned_int_t = std::enable_if_t::value>; template using to_unsigned_t = typename to_unsigned::type; } // namespace internal } // namespace yosupo namespace yosupo { struct Scanner { public: Scanner(const Scanner&) = delete; Scanner& operator=(const Scanner&) = delete; Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; } void read() {} template void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } int read_unsafe() { return 0; } template int read_unsafe(H& h, T&... t) { bool f = read_single(h); if (!f) return 0; return 1 + read_unsafe(t...); } int close() { return ::close(fd); } private: static constexpr int SIZE = 1 << 15; int fd = -1; std::array line; int st = 0, ed = 0; bool eof = false; bool read_single(std::string& ref) { if (!skip_space()) return false; ref = ""; while (true) { char c = top(); if (c <= ' ') break; ref += c; st++; } return true; } bool read_single(double& ref) { std::string s; if (!read_single(s)) return false; ref = std::stod(s); return true; } template ::value>* = nullptr> bool read_single(T& ref) { if (!skip_space<50>()) return false; ref = top(); st++; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(T& sref) { using U = internal::to_unsigned_t; if (!skip_space<50>()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } U ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); sref = neg ? -ref : ref; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(U& ref) { if (!skip_space<50>()) return false; ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); return true; } bool reread() { if (ed - st >= 50) return true; if (st > SIZE / 2) { std::memmove(line.data(), line.data() + st, ed - st); ed -= st; st = 0; } if (eof) return false; auto u = ::read(fd, line.data() + ed, SIZE - ed); if (u == 0) { eof = true; line[ed] = '\0'; u = 1; } ed += int(u); line[ed] = char(127); return true; } char top() { if (st == ed) { bool f = reread(); assert(f); } return line[st]; } template bool skip_space() { while (true) { while (line[st] <= ' ') st++; if (ed - st > TOKEN_LEN) return true; if (st > ed) st = ed; for (auto i = st; i < ed; i++) { if (line[i] <= ' ') return true; } if (!reread()) return false; } } }; struct Printer { public: template void write() {} template void write(const H& h, const T&... t) { if (F) write_single(sep); write_single(h); write(t...); } template void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fd(fileno(_fp)) {} ~Printer() { flush(); } int close() { flush(); return ::close(fd); } void flush() { if (pos) { auto res = ::write(fd, line.data(), pos); assert(res != -1); pos = 0; } } private: static std::array, 100> small; static std::array tens; static constexpr size_t SIZE = 1 << 15; int fd; std::array line; size_t pos = 0; std::stringstream ss; template ::value>* = nullptr> void write_single(const T& val) { if (pos == SIZE) flush(); line[pos++] = val; } template * = nullptr, std::enable_if_t::value>* = nullptr> void write_single(const T& val) { using U = internal::to_unsigned_t; if (val == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); U uval = val; if (val < 0) { write_single('-'); uval = -uval; } write_unsigned(uval); } template * = nullptr> void write_single(U uval) { if (uval == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); write_unsigned(uval); } template * = nullptr> static int calc_len(U x) { int i = (bsr(x) * 3 + 3) / 10; if (x < tens[i]) return i; else return i + 1; } template * = nullptr, std::enable_if_t<2 >= sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template * = nullptr, std::enable_if_t<4 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { std::array buf; memcpy(buf.data() + 6, small[uval % 100].data(), 2); memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2); memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2); memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2); if (uval >= 100000000) { if (uval >= 1000000000) { memcpy(line.data() + pos, small[uval / 100000000 % 100].data(), 2); pos += 2; } else { line[pos] = char('0' + uval / 100000000); pos++; } memcpy(line.data() + pos, buf.data(), 8); pos += 8; } else { size_t len = calc_len(uval); memcpy(line.data() + pos, buf.data() + (8 - len), len); pos += len; } } template * = nullptr, std::enable_if_t<8 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template < class U, std::enable_if_t::value>* = nullptr> void write_unsigned(U uval) { static std::array buf; size_t len = 0; while (uval > 0) { buf[len++] = char((uval % 10) + '0'); uval /= 10; } std::reverse(buf.begin(), buf.begin() + len); memcpy(line.data() + pos, buf.data(), len); pos += len; } void write_single(const std::string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template void write_single(const std::vector& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; std::array, 100> Printer::small = [] { std::array, 100> table; for (int i = 0; i <= 99; i++) { table[i][1] = char('0' + (i % 10)); table[i][0] = char('0' + (i / 10 % 10)); } return table; }(); std::array Printer::tens = [] { std::array table; for (int i = 0; i < 20; i++) { table[i] = 1; for (int j = 0; j < i; j++) { table[i] *= 10; } } return table; }(); } // namespace yosupo #include #include #include #include #include namespace yosupo { struct Xoshiro256StarStar { public: using result_type = uint64_t; Xoshiro256StarStar() : Xoshiro256StarStar(0) {} explicit Xoshiro256StarStar(uint64_t seed) { for (int i = 0; i < 4; i++) { uint64_t z = (seed += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; s[i] = z ^ (z >> 31); } } static constexpr result_type min() { return 0; } static constexpr result_type max() { return -1; } result_type operator()() { const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9; const uint64_t t = s[1] << 17; s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return result_starstar; } private: static uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } std::array s; }; namespace internal { template uint64_t uniform(uint64_t upper, G& gen) { static_assert(std::is_same::value, ""); static_assert(G::min() == 0, ""); static_assert(G::max() == uint64_t(-1), ""); if (!(upper & (upper + 1))) { return gen() & upper; } int log = bsr(upper); uint64_t mask = (log == 63) ? ~0ULL : (1ULL << (log + 1)) - 1; while (true) { uint64_t r = gen() & mask; if (r <= upper) return r; } } } // namespace internal Xoshiro256StarStar& global_gen() { static Xoshiro256StarStar gen( std::chrono::steady_clock::now().time_since_epoch().count()); return gen; } template T uniform(T lower, T upper, G& gen) { return T(lower + internal::uniform(uint64_t(upper) - uint64_t(lower), gen)); } template T uniform(T lower, T upper) { return uniform(lower, upper, global_gen()); } template bool uniform_bool(G& gen) { return internal::uniform(1, gen) == 1; } bool uniform_bool() { return uniform_bool(global_gen()); } template std::pair uniform_pair(T lower, T upper, G& gen) { assert(upper - lower >= 1); T a, b; do { a = uniform(lower, upper, gen); b = uniform(lower, upper, gen); } while (a == b); if (a > b) std::swap(a, b); return {a, b}; } template std::pair uniform_pair(T lower, T upper) { return uniform_pair(lower, upper, global_gen()); } } // namespace yosupo using namespace yosupo; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template using V = vector; template using VV = V>; #ifdef LOCAL ostream& operator<<(ostream& os, __int128_t x) { if (x < 0) { os << "-"; x *= -1; } if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } ostream& operator<<(ostream& os, __uint128_t x) { if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } template ostream& operator<<(ostream& os, const pair& p); template ostream& operator<<(ostream& os, const V& v); template ostream& operator<<(ostream& os, const deque& v); template ostream& operator<<(ostream& os, const array& a); template ostream& operator<<(ostream& os, const set& s); template ostream& operator<<(ostream& os, const map& m); template ostream& operator<<(ostream& os, const pair& p) { return os << "P(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const V& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const deque& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const array& a) { os << "["; bool f = false; for (auto d : a) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const set& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const multiset& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const map& s) { os << "{"; bool f = false; for (auto p : s) { if (f) os << ", "; f = true; os << p.first << ": " << p.second; } return os << "}"; } struct PrettyOS { ostream& os; bool first; template auto operator<<(T&& x) { if (!first) os << ", "; first = false; os << x; return *this; } }; template void dbg0(T&&... t) { (PrettyOS{cerr, true} << ... << t); } #define dbg(...) \ do { \ cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \ dbg0(__VA_ARGS__); \ cerr << endl; \ } while (false); #else #define dbg(...) #endif struct Nimber64; Nimber64 mul_naive(Nimber64 l, Nimber64 r); struct Nimber64 { const static V factor; const static array, 256> small; const static array, 8>, 8> precalc; ull v; Nimber64() : v(0) {} Nimber64(ull _v) : v(_v) {} const Nimber64 operator+(Nimber64 r) const { return v ^ r.v; } const Nimber64 operator-(Nimber64 r) const { return v ^ r.v; } const Nimber64 operator*(Nimber64 r) const { Nimber64 ans; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { ull x = (v >> (8 * i)) % 256; ull y = (r.v >> (8 * j)) % 256; ans += precalc[i][j][small[x][y]]; } } return ans; } const Nimber64 operator/(Nimber64 r) const { auto ri = r.pow(ull(-1) - 1); assert((r * ri) == Nimber64(1)); return (*this) * ri; } bool operator==(Nimber64 r) const { return v == r.v; } bool operator!=(Nimber64 r) const { return v != r.v; } Nimber64& operator+=(Nimber64 r) { return *this = *this + r; } Nimber64& operator-=(Nimber64 r) { return *this = *this - r; } Nimber64& operator*=(Nimber64 r) { return *this = *this * r; } Nimber64& operator/=(Nimber64 r) { return *this = *this / r; } Nimber64 pow(ull n) const { Nimber64 x = *this, r = 1; while (n) { if (n & 1) r = r * x; x = x * x; n >>= 1; } return r; } ull discrete_logarithm(Nimber64 y) { ull rem = 0, mod = 1; for (ull p : factor) { ull STEP = 1; while (4 * STEP * STEP < p) STEP *= 2; auto inside = [&](Nimber64 x, Nimber64 z) { unordered_map mp; Nimber64 big = 1; // x^m for (int i = 0; i < int(STEP); i++) { mp[z.v] = i; z *= x; big *= x; } Nimber64 now = 1; for (ull step = 0; step < ull(p + 10); step += STEP) { now *= big; // check [step + 1, step + STEP] if (mp.find(now.v) != mp.end()) { return (step + STEP) - mp[now.v]; } } return ull(-1); }; ull q = ull(-1) / p; ull res = inside((*this).pow(q), y.pow(q)); if (res == ull(-1)) { return ull(-1); } res %= p; // mod p = v if (mod == 1) { rem = res; mod = p; } else { while (rem % p != res) rem += mod; mod *= p; } } return rem; } bool is_primitive_root() const { for (ull p : factor) { if ((*this).pow(ull(-1) / p).v == 1) return false; } return true; } }; const V Nimber64::factor = { 6700417, 65537, 641, 257, 17, 5, 3, }; Nimber64 mul_naive(Nimber64 l, Nimber64 r) { ull a = l.v, b = r.v; if (a < b) swap(a, b); if (b == 0) return 0; if (b == 1) return a; int p = 32; while (max(a, b) < (1ULL << p)) p /= 2; ull power = 1ULL << p; if (a >= power && b >= power) { Nimber64 ans; ans += mul_naive(a % power, b % power); ans += mul_naive(a / power, b % power).v * power; ans += mul_naive(a % power, b / power).v * power; auto x = mul_naive(a / power, b / power); ans += x.v * power; ans += mul_naive(x.v, power / 2); return ans; } else { return Nimber64(mul_naive(a / power, b).v * power) + mul_naive(a % power, b); } }; const array, 256> Nimber64::small = []() { array, 256> small; for (int i = 0; i < 256; i++) { for (int j = 0; j < 256; j++) { small[i][j] = (unsigned char)(mul_naive(i, j).v); } } return small; }(); const array, 8>, 8> Nimber64::precalc = []() { array, 8>, 8> precalc; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { for (int k = 0; k < 256; k++) { precalc[i][j][k] = mul_naive(mul_naive(1ULL << (8 * i), 1ULL << (8 * j)), k); } } } return precalc; }(); struct Nimber32 { const static V factor; uint v; Nimber32() : v(0) {} Nimber32(uint _v) : v(_v) {} const Nimber32 operator+(Nimber32 r) const { return v ^ r.v; } const Nimber32 operator-(Nimber32 r) const { return v ^ r.v; } const Nimber32 operator*(Nimber32 r) const { Nimber32 ans; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { uint x = (v >> (8 * i)) % 256; uint y = (r.v >> (8 * j)) % 256; ans += uint(Nimber64::precalc[i][j][Nimber64::small[x][y]].v); } } return ans; } bool operator==(Nimber32 r) const { return v == r.v; } bool operator!=(Nimber32 r) const { return v != r.v; } Nimber32& operator+=(Nimber32 r) { return *this = *this + r; } Nimber32& operator-=(Nimber32 r) { return *this = *this - r; } Nimber32& operator*=(Nimber32 r) { return *this = *this * r; } }; struct Nimber16 { const static V factor; ushort v; Nimber16() : v(0) {} Nimber16(ushort _v) : v(_v) {} const Nimber16 operator+(Nimber16 r) const { return v ^ r.v; } const Nimber16 operator-(Nimber16 r) const { return v ^ r.v; } const Nimber16 operator*(Nimber16 r) const { Nimber16 ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { uint x = (v >> (8 * i)) % 256; uint y = (r.v >> (8 * j)) % 256; ans += ushort(Nimber64::precalc[i][j][Nimber64::small[x][y]].v); } } return ans; } bool operator==(Nimber16 r) const { return v == r.v; } bool operator!=(Nimber16 r) const { return v != r.v; } Nimber16& operator+=(Nimber16 r) { return *this = *this + r; } Nimber16& operator-=(Nimber16 r) { return *this = *this - r; } Nimber16& operator*=(Nimber16 r) { return *this = *this * r; } }; Scanner sc = Scanner(stdin); Printer pr = Printer(stdout); int naive(VV mp, int x, int y, int z) { int n = int(mp.size()); V idx(n); iota(idx.begin(), idx.end(), 0); int ans = n + 1; do { bool f0 = false, f1 = false, f2 = false; for (int i = 0; i < n; i++) { if (i && !mp[idx[i - 1]][idx[i]]) break; if (idx[i] == x) f0 = true; if (idx[i] == y) f1 = true; if (idx[i] == z) f2 = true; if (mp[idx[i]][idx[0]] && f0 && f1 && f2) { ans = min(ans, i + 1); } } } while (next_permutation(idx.begin(), idx.end())); if (ans == n + 1) ans = -1; return ans; } V naive_path(VV mp, int x, int y, int z) { int n = int(mp.size()); V idx(n); iota(idx.begin(), idx.end(), 0); V ans; do { if (idx[0] != x) continue; bool f0 = false, f1 = false, f2 = false; for (int i = 0; i < n; i++) { if (i && !mp[idx[i - 1]][idx[i]]) break; if (idx[i] == x) f0 = true; if (idx[i] == y) f1 = true; if (idx[i] == z) f2 = true; if (mp[idx[i]][idx[0]] && f0 && f1 && f2) { V cur = {idx.begin(), idx.begin() + i + 1}; cur.push_back(idx[0]); if (ans.empty() || cur.size() < ans.size() || (cur.size() == ans.size() && cur < ans)) { ans = cur; } } } } while (next_permutation(idx.begin(), idx.end())); return ans; } /* - 始点s, 終点t, mid上の頂点をすべてちょうど一度ずつ通るパスを探索 - 無向グラフ, midはdistinctで間に辺が無いことを仮定 - return pair(パスの長さの最小 or 1, 最短パスのうち、sの次に訪れうる最小の頂点番号) */ pair find_path(const VV& g, int s, int t, V mid) { /* dbg(s, t, mid); for (auto v : g) { dbg(v); }*/ using T = Nimber16; int n = int(g.size()); int k = int(mid.size()); V is_mid(n, -1); for (int i = 0; i < k; i++) { is_mid[mid[i]] = i; } VV val(n, V(n)); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { val[i][j] = val[j][i] = uniform(0, -1); } } V> dp(1 << k, VV(n + 1, V(n))); /* dp[f][len][p]: 次の条件を満たすwalkを列挙、sum prod_{e in path} val[{e}] - tは最初のみに出てくる, sは出てこない - midは高々1度ずつ出てくる、fはmidが出現したかのbitmap - walk: (t -> ... -> p) - walkはmidを中点とする折返し(a -> (mid vertex) -> a)を含まない F_{2^p}ならサイクルがキャンセリングされる。最初から見ていき、初めて2度出てきた頂点ペアの間を反転する。 dp[true][true][i][x][*][x] != 0ならば答えi */ dp[0][0][t] += 1; for (int len = 0; len < n; len++) { int ans = n; for (int f = 0; f < (1 << k); f++) { VV dp2(k, V(n)); for (int p = 0; p < n; p++) { if (dp[f][len][p] == T(0)) continue; assert(is_mid[p] == -1); for (int q : g[p]) { if (q == t) continue; if (q == s) { if (f == ((1 << k) - 1)) { ans = min(ans, p); //return {len + k + 1, p}; } continue; } T v = dp[f][len][p] * val[p][q]; if (is_mid[q] != -1) { dp2[is_mid[q]][p] += v;; continue; } dp[f][len + 1][q] += v; } } for (int i = 0; i < k; i++) { if (f & (1 << i)) continue; int p = mid[i]; T sum = 0; for (auto x : dp2[i]) sum += x; for (int q : g[p]) { if (q == t) continue; T v = (sum - dp2[i][q]) * val[p][q]; if (v == T(0)) continue; if (q == s) { if ((f | (1 << i)) == ((1 << k) - 1)) { ans = min(ans, p); } continue; } dp[f | (1 << i)][len + 1][q] += v; } } } if (ans < n) { return {len + k + 1, ans}; } } return {-1, 0}; } pair find_path_rec(const VV& g, int s, int t, V mid, int times=2) { pair ans = {TEN(9), 0}; for (int i = 0; i < times; i++) { auto cans = find_path(g, s, t, mid); if (cans.first != -1) ans = min(ans, cans); } if (ans.first == TEN(9)) ans.first = -1; return ans; } /* int solve(VV mp, int x, int y, int z) { int n = int(mp.size()); // duplicate x VV mp2(n + 1, V(n + 1)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { mp2[i][j] = mp[i][j]; } } for (int i = 0; i < n; i++) { mp2[i][n] = mp2[n][i] = mp2[x][i]; } auto result = find_path(mp2, x, n, {y, z}); return result.first; } */ V solve_path(VV g, int x, int y, int z) { auto cg = [&]() { int n = int(g.size()); VV g2(g.size()); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j]) { g2[i].push_back(j); } } } return g2; }; int n = int(g.size()); { // duplicate x VV g2(n + 1, V(n + 1)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g2[i][j] = g[i][j]; } } for (int i = 0; i < n; i++) { g2[i][n] = g2[n][i] = g[x][i]; } g = g2; n++; } // x -> ... -> y -> ... -> z -> ... -> (n - 1) if (find_path_rec(cg(), x, n - 1, {y, z}).first == -1) return {}; V idx(n), ridx(n); iota(idx.begin(), idx.end(), 0); iota(ridx.begin(), ridx.end(), 0); V answer; answer.push_back(x); int s = x; while (s != n - 1) { V mid; if (y != s && idx[y] != -1) mid.push_back(idx[y]); if (z != s && idx[z] != -1) mid.push_back(idx[z]); auto result = find_path_rec(cg(), idx[s], idx[n - 1], mid); // dbg(result); assert(result.first != -1); int s2 = ridx[result.second]; answer.push_back(s2); // remove s { V idx2 = idx; int m = 0; for (int i = 0; i < n; i++) { if (idx2[i] > idx2[s]) idx2[i]--; m = max(m, idx2[i] + 1); } idx2[s] = -1; V ridx2(n, -1); for (int i = 0; i < n; i++) { if (idx2[i] != -1) ridx2[idx2[i]] = i; } VV g2(m, V(m)); for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { g2[i][j] = g[idx[ridx2[i]]][idx[ridx2[j]]]; } } idx = idx2; ridx = ridx2; g = g2; } s = s2; } answer.back() = x; return answer; } int main() { int n, m; sc.read(n, m); VV mp(n, V(n, true)); for (int i = 0; i < n; i++) { mp[i][i] = false; } int x, y, z; sc.read(x, y, z); x--; y--; z--; for (int i = 0; i < m; i++) { int a, b; sc.read(a, b); a--; b--; mp[a][b] = mp[b][a] = false; } // auto expect = solve2(mp, x, y, z); auto answer = solve_path(mp, x, y, z); dbg(answer); // dbg(answer, expect); // pr.writeln(answer); if (answer.empty()) { pr.writeln(-1); return 0; } int len = int(answer.size() - 1); pr.writeln(len); for (int i = 0; i <= len; i++) { pr.write(answer[i] + 1); if (i != len) pr.write(' '); } pr.writeln(); /* while (true) { int n = uniform(3, 10); VV mp(n, V(n, true)); for (int i = 0; i < n; i++) { mp[i][i] = false; } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (uniform(0, 10) >= 5) { mp[i][j] = mp[j][i] = false; } } } // mp[0][1] = mp[1][0] = false; // mp[2][0] = mp[0][2] = false; mp[1][2] = mp[2][1] = false; auto expect = naive_path(mp, 0, 1, 2); auto actual = solve_path(mp, 0, 1, 2); if (expect != actual) { dbg(n); for (auto v : mp) { dbg(v); } dbg(expect, actual); assert(false); } }*/ return 0; }