//#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 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; }(); Scanner sc = Scanner(stdin); Printer pr = Printer(stdout); const int MN = 10; Nimber64 dp[2][2][MN][MN][MN]; //set> dp[2][2][MN][MN][MN]; 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; } 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); } } /* dp[f][g][i][j][k]: 次の条件を満たすwalkを列挙、sum prod_{e in path} val[{e}] - (f, g)=(y, z)を通ったか - walk: (x -> ... -> j -> k) - walkは折返し(a -> b -> a)を含まない F_{2^p}ならサイクルがキャンセリングされるのでdp[true][true][i][x][*][x] != 0ならば答えi */ dp[0][0][0][n][x] += 1; //dp[0][0][0][n][x].insert({x}); for (int len = 0; len <= n + 1; len++) { for (int f = 0; f <= 1; f++) { for (int g = 0; g <= 1; g++) { for (int j = 0; j <= n; j++) { for (int k = 0; k < n; k++) { if (dp[f][g][len][j][k] == Nimber64(0)) continue; //if (dp[f][g][len][j][k].empty()) continue; //dbg(f, g, len, j, k); //dbg(dp[f][g][len][j][k]); if (len && f && g && k == x) { pr.writeln(len); return 0; } for (int l = 0; l < n; l++) { if (l == j) continue; if (!mp[k][l]) continue; int nf = f || (l == y); int ng = g || (l == z); dp[nf][ng][len+1][k][l] += dp[f][g][len][j][k] * val[k][l]; /*for (auto v : dp[f][g][len][j][k]) { v.push_back(l); if (dp[nf][ng][len + 1][k][l].count(v)) { dp[nf][ng][len + 1][k][l].erase(v); } else { dp[nf][ng][len+1][k][l].insert(v); } }*/ } } } } } } pr.writeln(-1); return 0; }