結果
| 問題 | No.2948 move move rotti |
| ユーザー |
 kk2
|
| 提出日時 | 2024-10-25 22:09:54 |
| 言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 248 ms / 4,000 ms |
| コード長 | 26,854 bytes |
| コンパイル時間 | 3,406 ms |
| コンパイル使用メモリ | 234,356 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-25 22:10:12 |
| 合計ジャッジ時間 | 6,218 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 80 ms
6,816 KB |
| testcase_04 | AC | 54 ms
6,820 KB |
| testcase_05 | AC | 2 ms
6,816 KB |
| testcase_06 | AC | 2 ms
6,820 KB |
| testcase_07 | AC | 57 ms
6,820 KB |
| testcase_08 | AC | 194 ms
6,824 KB |
| testcase_09 | AC | 193 ms
6,820 KB |
| testcase_10 | AC | 2 ms
6,820 KB |
| testcase_11 | AC | 2 ms
6,820 KB |
| testcase_12 | AC | 6 ms
6,820 KB |
| testcase_13 | AC | 28 ms
6,820 KB |
| testcase_14 | AC | 24 ms
6,824 KB |
| testcase_15 | AC | 34 ms
6,820 KB |
| testcase_16 | AC | 172 ms
6,816 KB |
| testcase_17 | AC | 93 ms
6,816 KB |
| testcase_18 | AC | 228 ms
6,820 KB |
| testcase_19 | AC | 116 ms
6,820 KB |
| testcase_20 | AC | 157 ms
6,820 KB |
| testcase_21 | AC | 226 ms
6,820 KB |
| testcase_22 | AC | 70 ms
6,820 KB |
| testcase_23 | AC | 248 ms
6,824 KB |
| testcase_24 | AC | 55 ms
6,816 KB |
| testcase_25 | AC | 82 ms
6,820 KB |
| testcase_26 | AC | 2 ms
6,816 KB |
| testcase_27 | AC | 2 ms
6,820 KB |
| testcase_28 | AC | 4 ms
6,820 KB |
| testcase_29 | AC | 2 ms
6,820 KB |
| testcase_30 | AC | 2 ms
6,816 KB |
ソースコード
#ifndef GRAPH_GRAPH_TEMPLATE_HPP
#define GRAPH_GRAPH_TEMPLATE_HPP 1
#include <cassert>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>
#ifndef TYPE_TRAITS_HPP
#define TYPE_TRAITS_HPP 1
#include <istream>
#include <ostream>
#include <type_traits>
namespace kk2 {
template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
or std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value
or std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_integral =
typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned =
typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template <typename T>
using to_unsigned =
typename std::conditional<is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;
template <typename T>
using is_function_pointer =
typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
std::true_type,
std::false_type>::type;
template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};
template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};
template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;
namespace type_traits {
struct istream_tag {};
struct ostream_tag {};
} // namespace type_traits
template <typename T> using is_standard_istream = std::is_same<T, std::istream>;
template <typename T> using is_standard_ostream = std::is_same<T, std::ostream>;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;
template <typename T>
using is_istream =
typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_ostream =
typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;
} // namespace kk2
#endif // TYPE_TRAITS_HPP
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
namespace graph {
struct empty {};
template <class T> struct _Edge {
int from, to, id;
T cost;
_Edge(int to_, T cost_, int from_ = -1, int id_ = -1)
: from(from_),
to(to_),
id(id_),
cost(cost_) {}
_Edge() : from(-1), to(-1), id(-1), cost() {}
operator int() const { return to; }
_Edge rev() const { return _Edge(from, cost, to, id); }
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const _Edge &e) {
if constexpr (std::is_same_v<T, empty>) return os << e.from << " -> " << e.to;
else return os << e.from << " -> " << e.to << " : " << e.cost;
}
};
template <class T> using _Edges = std::vector<_Edge<T>>;
template <class T, bool is_directed> struct AdjacencyList : std::vector<_Edges<T>> {
using value_type = T;
using edge_type = _Edge<T>;
constexpr static bool directed() { return is_directed; }
AdjacencyList() = default;
AdjacencyList(int n_) : std::vector<_Edges<T>>(n_) {}
AdjacencyList(int n_, int m_) : std::vector<_Edges<T>>(n_), edges(m_) {}
AdjacencyList(int n_, const _Edges<T> &edges_) : std::vector<_Edges<T>>(n_), edges(edges_) {
for (auto &&e : edges) {
(*this)[e.from].emplace_back(e);
if constexpr (!is_directed) (*this)[e.to].emplace_back(e);
}
}
_Edges<T> edges;
int num_vertices() const { return (int)this->size(); }
int num_edges() const { return (int)edges.size(); }
template <class IStream, is_istream_t<IStream> * = nullptr>
AdjacencyList &input(IStream &is, bool oneindexed = false) {
for (int i = 0; i < num_edges(); i++) {
int u, v;
T w{};
is >> u >> v;
if constexpr (!std::is_same_v<T, empty>) is >> w;
if (oneindexed) --u, --v;
_add_edge<true>(u, v, w, i);
}
return *this;
}
void edge_clear() {
for (auto &v : *this) v.clear();
edges.clear();
}
void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); }
private:
template <bool update = false>
void _add_edge(int from, int to, T cost, int id) {
(*this)[from].emplace_back(to, cost, from, id);
if constexpr (!is_directed) (*this)[to].emplace_back(from, cost, to, id);
if constexpr (update) edges[id] = _Edge<T>(to, cost, from, id);
else edges.emplace_back(to, cost, from, id);
}
};
template <class T> struct _pair {
T cost;
int id;
_pair(T cost_, int id_) : cost(cost_), id(id_) {}
_pair() : cost(), id(-1) {}
operator bool() const { return id != -1; }
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const _pair &p) {
if constexpr (std::is_same_v<T, empty>) return os;
else return os << p.cost;
}
};
template <class T> using _pairs = std::vector<_pair<T>>;
template <class T, bool is_directed> struct AdjacencyMatrix : std::vector<_pairs<T>> {
using value_type = T;
using edge_type = _pair<T>;
constexpr static bool directed() { return is_directed; }
AdjacencyMatrix() = default;
AdjacencyMatrix(int n_) : std::vector<_pairs<T>>(n_, _pairs<T>(n_)) {}
AdjacencyMatrix(int n_, int m_) : std::vector<_pairs<T>>(n_, _pairs<T>(n_)), edges(m_) {}
AdjacencyMatrix(int n_, const _Edges<T> &edges_)
: std::vector<_pairs<T>>(n_, _pairs<T>(n_)),
edges(edges_) {
for (auto &&e : edges) {
(*this)[e.from][e.to] = _pair<T>(e.cost, e.id);
if constexpr (!is_directed) (*this)[e.to][e.from] = _pair<T>(e.cost, e.id);
}
}
template <class IStream, is_istream_t<IStream> * = nullptr>
AdjacencyMatrix &input(IStream &is, bool oneindexed = false) {
for (int i = 0; i < num_edges(); i++) {
int u, v;
T w{};
is >> u >> v;
if constexpr (!std::is_same_v<T, empty>) is >> w;
if (oneindexed) --u, --v;
_add_edge<true>(u, v, w, i);
}
return *this;
}
_Edges<T> edges;
int num_vertices() const { return (int)this->size(); }
int num_edges() const { return (int)edges.size(); }
void edge_clear() {
for (auto &&e : edges) {
(*this)[e.from][e.to] = _pair<T>(e.cost, e.id);
if constexpr (!is_directed) (*this)[e.to][e.from] = _pair<T>(e.cost, e.id);
}
edges.clear();
}
void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); }
private:
template <bool update = false>
void _add_edge(int from, int to, T cost, int id) {
(*this)[from][to] = _pair<T>(cost, id);
if constexpr (!is_directed) (*this)[to][from] = _pair<T>(cost, id);
if constexpr (update) edges[id] = _Edge<T>(to, cost, from, id);
else edges.emplace_back(to, cost, from, id);
}
};
template <class G>
G reverse(const G &g) {
G res(g.num_vertices());
for (auto &&e : g.edges) res.add_edge(e.to, e.from, e.cost);
return res;
}
template <class T, class IStream, is_istream_t<IStream> * = nullptr>
_Edges<T> &input(_Edges<T> &edges, bool is_one_indexed, IStream &is) {
for (int i = 0; i < (int)edges.size(); i++) {
int u, v;
T w{};
is >> u >> v;
if (is_one_indexed) --u, --v;
if constexpr (!std::is_same_v<T, empty>) is >> w;
edges[i] = _Edge<T>(v, w, u, i);
}
return edges;
}
} // namespace graph
template <typename T> using WAdjList = graph::AdjacencyList<T, false>;
template <typename T> using DWAdjList = graph::AdjacencyList<T, true>;
using AdjList = graph::AdjacencyList<graph::empty, false>;
using DAdjList = graph::AdjacencyList<graph::empty, true>;
template <typename T> using WAdjMat = graph::AdjacencyMatrix<T, false>;
template <typename T> using DWAdjMat = graph::AdjacencyMatrix<T, true>;
using AdjMat = graph::AdjacencyMatrix<graph::empty, false>;
using DAdjMat = graph::AdjacencyMatrix<graph::empty, true>;
template <typename T> using WEdge = graph::_Edge<T>;
template <typename T> using WEdges = graph::_Edges<T>;
using Edge = graph::_Edge<graph::empty>;
using Edges = graph::_Edges<graph::empty>;
using graph::input;
using graph::reverse;
} // namespace kk2
#endif // GRAPH_GRAPH_TEMPLATE_HPP
// #include <kk2/graph/graph.hpp>
#ifndef BIT_BITCOUNT_HPP
#define BIT_BITCOUNT_HPP 1
#include <cassert>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <typename T> int ctz(T x) {
static_assert(is_integral<T>::value);
assert(x != T(0));
if constexpr (sizeof(T) <= 4) {
return __builtin_ctz(x);
} else if constexpr (sizeof(T) <= 8) {
return __builtin_ctzll(x);
} else {
if (x & 0xffffffffffffffff)
return __builtin_ctzll((unsigned long long)(x & 0xffffffffffffffff));
return 64 + __builtin_ctzll((unsigned long long)(x >> 64));
}
}
template <typename T> int clz(T x) {
static_assert(is_integral<T>::value);
assert(x != T(0));
if constexpr (sizeof(T) <= 4) {
return __builtin_clz(x);
} else if constexpr (sizeof(T) <= 8) {
return __builtin_clzll(x);
} else {
if (x >> 64) return __builtin_clzll((unsigned long long)(x >> 64));
return 64 + __builtin_clzll((unsigned long long)(x & 0xffffffffffffffff));
}
}
template <typename T> int popcount(T x) {
static_assert(is_integral<T>::value);
if constexpr (sizeof(T) <= 4) {
return __builtin_popcount(x);
} else if constexpr (sizeof(T) <= 8) {
return __builtin_popcountll(x);
} else {
return __builtin_popcountll((unsigned long long)(x >> 64))
+ __builtin_popcountll((unsigned long long)(x & 0xffffffffffffffff));
}
}
}; // namespace kk2
#endif // BIT_BITCOUNT_HPP
// #include <kk2/bit/bitcount.hpp>
#ifndef TEMPLATE
#define TEMPLATE 1
// #pragma GCC optimize("O3,unroll-loops")
// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// #include "../type_traits/type_traits.hpp"
#ifndef TEMPLATE_FASTIO_HPP
#define TEMPLATE_FASTIO_HPP 1
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
namespace fastio {
#define INPUT_FILE "in.txt"
#define OUTPUT_FILE "out.txt"
struct Scanner : type_traits::istream_tag {
private:
static constexpr size_t INPUT_BUF = 1 << 17;
size_t pos = 0, end = 0;
static char buf[INPUT_BUF];
FILE *fp;
public:
Scanner() : fp(stdin) {}
Scanner(const char *file) : fp(fopen(file, "r")) {}
~Scanner() {
if (fp != stdin) fclose(fp);
}
char now() {
if (pos == end) {
while (!(end = fread(buf, 1, INPUT_BUF, fp))) {}
if (end != INPUT_BUF) buf[end] = '\0';
pos = 0;
}
return buf[pos];
}
void skip_space() {
while (isspace(now())) ++pos;
}
template <class T, is_unsigned_t<T> * = nullptr> T next_unsigned_integral() {
skip_space();
T res{};
while (isdigit(now())) {
res = res * 10 + (now() - '0');
++pos;
}
return res;
}
template <class T, is_signed_t<T> * = nullptr> T next_signed_integral() {
skip_space();
if (now() == '-') {
++pos;
return T(-next_unsigned_integral<typename to_unsigned<T>::type>());
} else return (T)next_unsigned_integral<typename to_unsigned<T>::type>();
}
char next_char() {
skip_space();
auto res = now();
++pos;
return res;
}
std::string next_string() {
skip_space();
std::string res;
while (true) {
char c = now();
if (isspace(c) or c == '\0') break;
res.push_back(now());
++pos;
}
return res;
}
template <class T, is_unsigned_t<T> * = nullptr> Scanner &operator>>(T &x) {
x = next_unsigned_integral<T>();
return *this;
}
template <class T, is_signed_t<T> * = nullptr> Scanner &operator>>(T &x) {
x = next_signed_integral<T>();
return *this;
}
Scanner &operator>>(char &x) {
x = next_char();
return *this;
}
Scanner &operator>>(std::string &x) {
x = next_string();
return *this;
}
};
struct endl_struct_t {};
struct Printer : type_traits::ostream_tag {
private:
static char helper[10000][5];
static char leading_zero[10000][5];
constexpr static size_t OUTPUT_BUF = 1 << 17;
static char buf[OUTPUT_BUF];
size_t pos = 0;
FILE *fp;
template <class T> static constexpr void div_mod(T &a, T &b, T mod) {
a = b / mod;
b -= a * mod;
}
static void init() {
buf[0] = '\0';
for (size_t i = 0; i < 10000; ++i) {
leading_zero[i][0] = i / 1000 + '0';
leading_zero[i][1] = i / 100 % 10 + '0';
leading_zero[i][2] = i / 10 % 10 + '0';
leading_zero[i][3] = i % 10 + '0';
leading_zero[i][4] = '\0';
size_t j = 0;
if (i >= 1000) helper[i][j++] = i / 1000 + '0';
if (i >= 100) helper[i][j++] = i / 100 % 10 + '0';
if (i >= 10) helper[i][j++] = i / 10 % 10 + '0';
helper[i][j++] = i % 10 + '0';
helper[i][j] = '\0';
}
}
public:
Printer() : fp(stdout) { init(); }
Printer(const char *file) : fp(fopen(file, "w")) { init(); }
~Printer() {
write();
if (fp != stdout) fclose(fp);
}
void write() {
fwrite(buf, 1, pos, fp);
pos = 0;
}
void flush() {
write();
fflush(fp);
}
void put_char(char c) {
if (pos == OUTPUT_BUF) write();
buf[pos++] = c;
}
void put_cstr(const char *s) {
while (*s) put_char(*(s++));
}
void put_u32(uint32_t x) {
uint32_t y;
if (x >= 100000000) { // 10^8
div_mod<uint32_t>(y, x, 100000000);
put_cstr(helper[y]);
div_mod<uint32_t>(y, x, 10000);
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= 10000) { // 10^4
div_mod<uint32_t>(y, x, 10000);
put_cstr(helper[y]);
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i32(int32_t x) {
if (x < 0) {
put_char('-');
put_u32(-x);
} else put_u32(x);
}
void put_u64(uint64_t x) {
uint64_t y;
if (x >= 1000000000000ull) { // 10^12
div_mod<uint64_t>(y, x, 1000000000000ull);
put_u32(y);
div_mod<uint64_t>(y, x, 100000000ull);
put_cstr(leading_zero[y]);
div_mod<uint64_t>(y, x, 10000ull);
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= 10000ull) { // 10^4
div_mod<uint64_t>(y, x, 10000ull);
put_u32(y);
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i64(int64_t x) {
if (x < 0) {
put_char('-');
put_u64(-x);
} else put_u64(x);
}
void put_u128(__uint128_t x) {
constexpr static __uint128_t pow10_10 = 10000000000ull;
constexpr static __uint128_t pow10_20 = pow10_10 * pow10_10;
__uint128_t y;
if (x >= pow10_20) { // 10^20
div_mod<__uint128_t>(y, x, pow10_20);
put_u64(uint64_t(y));
div_mod<__uint128_t>(y, x, __uint128_t(10000000000000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(1000000000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(100000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(10000ull));
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= __uint128_t(10000)) { // 10^4
div_mod<__uint128_t>(y, x, __uint128_t(10000));
put_u64(uint64_t(y));
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i128(__int128_t x) {
if (x < 0) {
put_char('-');
put_u128(-x);
} else put_u128(x);
}
template <class T, is_unsigned_t<T> * = nullptr> Printer &operator<<(T x) {
if constexpr (sizeof(T) <= 4) put_u32(x);
else if constexpr (sizeof(T) <= 8) put_u64(x);
else put_u128(x);
return *this;
}
template <class T, is_signed_t<T> * = nullptr> Printer &operator<<(T x) {
if constexpr (sizeof(T) <= 4) put_i32(x);
else if constexpr (sizeof(T) <= 8) put_i64(x);
else put_i128(x);
return *this;
}
Printer &operator<<(char x) {
put_char(x);
return *this;
}
Printer &operator<<(const std::string &x) {
for (char c : x) put_char(c);
return *this;
}
Printer &operator<<(const char *x) {
put_cstr(x);
return *this;
}
// std::cout << std::endl; は関数ポインタを渡しているらしい
Printer &operator<<(endl_struct_t) {
put_char('\n');
flush();
return *this;
}
};
char Scanner::buf[Scanner::INPUT_BUF];
char Printer::buf[Printer::OUTPUT_BUF];
char Printer::helper[10000][5];
char Printer::leading_zero[10000][5];
} // namespace fastio
#if defined(INTERACTIVE) || defined(USE_STDIO)
auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;
#elif defined(KK2)
fastio::Scanner kin(INPUT_FILE);
fastio::Printer kout(OUTPUT_FILE);
fastio::endl_struct_t kendl;
#else
fastio::Scanner kin;
fastio::Printer kout;
fastio::endl_struct_t kendl;
#endif
} // namespace kk2
#endif // TEMPLATE_FASTIO_HPP
// #include "fastio.hpp"
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;
template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;
constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;
namespace kk2 {
template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
if constexpr (sizeof...(sizes) == 0) {
return std::vector<T>(first);
} else {
return std::vector<decltype(make_vector(sizes...))>(first, make_vector(sizes...));
}
}
template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
std::fill(std::begin(v), std::end(v), T(x));
}
template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
for (auto &u : v) fill_all(u, x);
}
} // namespace kk2
template <class T, class S> inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S> inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
#define rep1(a) for (i64 _ = 0; _ < (i64)(a); ++_)
#define rep2(i, a) for (i64 i = 0; i < (i64)(a); ++i)
#define rep3(i, a, b) for (i64 i = (a); i < (i64)(b); ++i)
#define repi2(i, a) for (i64 i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (i64 i = (a) - 1; i >= (i64)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)
#define fi first
#define se second
#define all(p) std::begin(p), std::end(p)
using kk2::kendl;
using kk2::kin;
using kk2::kout;
struct IoSetUp {
IoSetUp() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
} iosetup;
template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
os << p.first << ' ' << p.second;
return os;
}
template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); }
return os;
}
template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
void Yes(bool b = 1) {
kout << (b ? "Yes\n" : "No\n");
}
void No(bool b = 1) {
kout << (b ? "No\n" : "Yes\n");
}
void YES(bool b = 1) {
kout << (b ? "YES\n" : "NO\n");
}
void NO(bool b = 1) {
kout << (b ? "NO\n" : "YES\n");
}
void yes(bool b = 1) {
kout << (b ? "yes\n" : "no\n");
}
void no(bool b = 1) {
kout << (b ? "no\n" : "yes\n");
}
#endif // TEMPLATE
// #include <kk2/template/template.hpp>
using namespace std;
void solve() {
int n, m, k;
kin >> n >> m >> k;
vc<int> x(k);
kin >> x;
for (auto& e : x) --e;
kk2::AdjMat g(n, m);
g.input(kin, true);
{
vvvc<bool> can_visited(k, vvc<bool>(n, vc<bool>(n)));
rep (i, k) {
vvc<bool> dist(1 << n, vc<bool>(n));
dist[1 << x[i]][x[i]] = true;
queue<pi> q;
q.emplace(1 << x[i], x[i]);
while (!q.empty()) {
auto [s, u] = q.front();
q.pop();
rep (v, n) {
if (~s >> v & 1 and g[u][v]) {
if (!dist[s ^ (1 << v)][v]) {
dist[s ^ (1 << v)][v] = true;
q.emplace(s ^ (1 << v), v);
}
}
}
}
rep (bit, 1 << n) {
rep (v, n) {
if (dist[bit][v]) {
can_visited[i][v][kk2::popcount(bit) - 1] = true;
}
}
}
}
rep (collect, n) {
auto ok = [&]() -> bool {
rep (step, n) {
auto ok2 = [&]() -> bool {
rep (i, k) {
if (!can_visited[i][collect][step]) return false;
}
return true;
};
if (ok2()) return true;
}
return false;
};
if (ok()) {
Yes();
return;
}
}
No();
}
}
int main() {
int t = 1;
// kin >> t;
rep (t) solve();
return 0;
}
// converted!!