You are given three strings A, B and C. Check whether they form a word chain.

More formally, determine whether both of the following are true:

* The last character in A and the initial character in B are the same.
* The last character in B and the initial character in C are the same.



If both are true, print `YES`. Otherwise, print `NO`.

Constraints

* A, B and C are all composed of lowercase English letters (`a` - `z`).
* 1 ≤ |A|, |B|, |C| ≤ 10, where |A|, |B| and |C| are the lengths of A, B and C, respectively.

Input

Input is given from Standard Input in the following format:


A B C


Output

Print `YES` or `NO`.

Examples

Input

rng gorilla apple


Output

YES


Input

yakiniku unagi sushi


Output

NO


Input

a a a


Output

YES


Input

aaaaaaaaab aaaaaaaaaa aaaaaaaaab


Output

NO
#include <bits/stdc++.h>
using namespace std;
class Large_Integer {
 private:
  static const long long shinsuu = 7;
  long long sign;
  vector<long long> numbers;
  static vector<long long> plusVector(vector<long long> a,
                                      vector<long long> b) {
    vector<long long> ans(max(a.size(), b.size()), 0);
    for (long long i = 0; i < ans.size(); i++) {
      if (i < a.size()) ans[i] += a[i];
      if (i < b.size()) ans[i] += b[i];
      if (i + 1 < ans.size()) {
        ans[i + 1] += (ans[i] / Large_Integer::shinsuu);
      }
      ans[i] %= Large_Integer::shinsuu;
    }
    return ans;
  }
  static vector<long long> ToVLL(Large_Integer const& a, long long const& min) {
    long long i;
    vector<long long> ans;
    if (a.sign == 1) {
      ans = vector<long long>(max(min, (long long)a.numbers.size()) + 5, 0);
      for (i = 0; i < a.numbers.size(); i++) {
        ans[i] += a.numbers[i];
      }
    } else {
      ans = vector<long long>(max(min, (long long)a.numbers.size()) + 5,
                              Large_Integer::shinsuu - 1);
      for (i = 0; i < a.numbers.size(); i++) {
        ans[i] -= a.numbers[i];
      }
      ans = Large_Integer::plusVector(ans, vector<long long>(1, 1));
    }
    return ans;
  }
  static Large_Integer ToInteger(vector<long long> const& a) {
    Large_Integer ans;
    long long i, j, k, n;
    n = a.size();
    if (a[n - 1] == Large_Integer::shinsuu - 1) {
      auto temp = vector<long long>(n, Large_Integer::shinsuu - 1);
      temp = Large_Integer::plusVector(a, temp);
      for (i = 0; i < temp.size(); i++) {
        temp[i] -= Large_Integer::shinsuu;
        temp[i] *= -1;
      }
      ans.sign = -1;
      ans.numbers = temp;
      ans.Syusei();
    } else {
      ans.sign = 1;
      ans.numbers = a;
      ans.Syusei();
    }
    return ans;
  }
  Large_Integer operator<<(Large_Integer const& a) const {
    long long shift = a.to_LongLong(), i;
    if (shift < 0) {
      return *this >> (shift * -1);
    }
    Large_Integer ans = *this;
    ans.numbers = vector<long long>(this->numbers.size() + shift, 0);
    for (i = 0; i < this->numbers.size(); i++) {
      ans.numbers[i + shift] += this->numbers[i];
    }
    ans.Syusei();
    return ans;
  }
  Large_Integer operator>>(Large_Integer const& a) const {
    long long shift = a.to_LongLong(), i;
    if (shift < 0) {
      return *this << (shift * -1);
    }
    Large_Integer ans = *this;
    ans.numbers = vector<long long>(
        max((long long)0, (long long)this->numbers.size() - shift), 0);
    for (i = 0; i < this->numbers.size(); i++) {
      if (i - shift >= 0) {
        ans.numbers[i - shift] = this->numbers[i];
      }
    }
    ans.Syusei();
    return ans;
  }
  Large_Integer operator*(long long const& b) const {
    Large_Integer ans;
    ans.sign = this->sign;
    ans.numbers = vector<long long>(this->numbers.size() + 2, 0);
    long long i, a = b;
    if (a < 0) {
      a *= -1;
      ans.sign *= -1;
    }
    for (i = 0; i < this->numbers.size(); i++) {
      ans.numbers[i] = a * this->numbers[i];
    }
    for (i = 0; i < ans.numbers.size(); i++) {
      if (i + 1 < ans.numbers.size()) {
        ans.numbers[i + 1] = (ans.numbers[i] / Large_Integer::shinsuu);
      }
      ans.numbers[i] %= Large_Integer::shinsuu;
    }
    return ans;
  }
  void Syusei() {
    long long i, j, k;
    if (abs(this->sign) != 1) {
      j = 0;
      j = 1 / j;
    }
    k = 0;
    for (i = 0; i < this->numbers.size(); i++) {
      if (this->numbers[i] < 0) {
        j = 0;
        j = 1 / j;
      }
      if (i + 1 < this->numbers.size()) {
        this->numbers[i + 1] += (this->numbers[i] / Large_Integer::shinsuu);
      }
      this->numbers[i] %= Large_Integer::shinsuu;
      if (this->numbers[i] > 0) k = i + 1;
    }
    vector<long long> ans(k, 0);
    for (i = 0; i < k; i++) {
      ans[i] = this->numbers[i];
    }
    this->numbers = ans;
    if (this->sign == -1 && this->numbers.size() == 0) {
      this->sign = 1;
    }
  }

 public:
  Large_Integer(Large_Integer const& b) { *this = b; }
  Large_Integer(long long const& b) {
    if (b < 0)
      this->sign = -1;
    else
      this->sign = 1;
    auto c = abs(b);
    while (c > 0) {
      this->numbers.push_back(c % this->shinsuu);
      c /= this->shinsuu;
    }
    this->Syusei();
  }
  Large_Integer() {
    this->sign = 1;
    this->numbers = vector<long long>(0);
  }
  long long to_LongLong() const {
    long long ans = 0, i;
    for (i = this->numbers.size() - 1; i >= 0; i--) {
      ans *= this->shinsuu;
      ans += this->numbers[i];
    }
    ans *= this->sign;
    return ans;
  }
  Large_Integer operator=(Large_Integer const& b) {
    this->sign = b.sign;
    this->numbers = b.numbers;
    return *this;
  }
  Large_Integer operator+(Large_Integer const& b) const {
    long long i, j;
    vector<long long> x, y;
    long long size = max(this->numbers.size(), b.numbers.size());
    x = Large_Integer::ToVLL(*this, size);
    y = Large_Integer::ToVLL(b, size);
    x = Large_Integer::plusVector(x, y);
    auto ans = Large_Integer::ToInteger(x);
    ans.Syusei();
    return ans;
  }
  Large_Integer operator+=(Large_Integer const& b) {
    return *this = (*this + b);
  }
  Large_Integer operator*(Large_Integer const& b) const {
    Large_Integer ans = 0;
    long long i;
    for (i = 0; i < b.numbers.size(); i++) {
      ans += ((*this * b.numbers[i]) << i);
    }
    return ans;
  }
  Large_Integer operator*=(Large_Integer const& b) {
    return *this = (*this * b);
  }
  Large_Integer operator-(Large_Integer const& b) const {
    return *this + (b * -1);
  }
  Large_Integer operator-=(Large_Integer const& b) {
    return *this = (*this - b);
  }
  bool operator<(Large_Integer const& b) const {
    long long i, j, k;
    if (this->sign < b.sign) {
      return true;
    }
    if (this->sign > b.sign) {
      return false;
    }
    if (this->sign == 1) {
      if (this->numbers.size() < b.numbers.size()) {
        return true;
      }
      if (this->numbers.size() > b.numbers.size()) {
        return false;
      }
      for (i = this->numbers.size() - 1; i >= 0; i--) {
        if (this->numbers[i] < b.numbers[i]) {
          return true;
        }
        if (this->numbers[i] > b.numbers[i]) {
          return false;
        }
      }
    }
  }
};
template <typename T>
class ArrayList : public vector<T> {
 public:
  ArrayList(long long const& size, T const& a) : vector<T>(size, a) {}
  ArrayList(long long const& size) : vector<T>(size) {}
  ArrayList() : vector<T>() {}
  T& operator[](long long const& index) { return vector<T>::at(index); }
};
class MYCP {
 public:
  static const long long MOD_CONST = (long long)1000 * 1000 * 1000 + 7;
  static long long DebugFlag;
  static string MakeString_LongLong(vector<long long> const& numbers,
                                    string const& str) {
    if (numbers.size() == 0) return "";
    string result = "" + to_string(numbers[0]);
    for (long long i = 1; i < numbers.size(); i++) {
      result += str;
      result += to_string(numbers[i]);
    }
    return result;
  }
  static string MakeString_LongLong(vector<long long> const& numbers) {
    if (numbers.size() == 0) return "";
    string result = "" + to_string(numbers[0]);
    for (long long i = 1; i < numbers.size(); i++) {
      result += " ";
      result += to_string(numbers[i]);
    }
    return result;
  }
  static string MakeString_VectorString(vector<string> const& str) {
    string result = "";
    for (long long i = 0; i < str.size(); i++) {
      result += str[i] + "\n";
    }
    return result;
  }
  static vector<string> MyReadLineSplit(long long n) {
    vector<string> str(n);
    for (long long i = 0; i < n; i++) {
      std::cin >> str[i];
    }
    return str;
  }
  static vector<long long> ReadInts(long long number) {
    vector<long long> a(number);
    for (int i = 0; i < number; i++) {
      std::cin >> a[i];
    }
    return a;
  }
  static bool PrimeCheck_Int(long long number) {
    if (number < 2) return false;
    for (unsigned long long i = 2; i * i <= number; i++) {
      if (number % i == 0) return false;
    }
    return true;
  }
  static vector<long long> MakePrimeList(long long n) {
    vector<long long> list;
    long long i, j, p;
    bool flag;
    for (i = 2; i <= n; i++) {
      flag = true;
      for (j = 0; j < list.size(); j++) {
        if (!(list[j] * list[j] <= i)) break;
        if (i % list[j] == 0) {
          flag = false;
          break;
        }
      }
      if (flag) list.push_back(i);
    }
    return list;
  }
  static vector<string> split(string const& str, char sep) {
    vector<std::string> v;
    auto first = str.begin();
    while (first != str.end()) {
      auto last = first;
      while (last != str.end() && *last != sep) last++;
      v.push_back(string(first, last));
      if (last != str.end()) last++;
      first = last;
    }
    return v;
  }
  template <typename T>
  static long long Sum(T const& a) {
    long long sum = 0;
    auto itr = a.begin();
    while (itr != a.end()) {
      sum += (*itr);
      itr++;
    }
    return sum;
  }
  static bool Komoji(char a) {
    if (a >= 'a' && a <= 'z') return true;
    return false;
  }
  static bool Oomoji(char a) {
    if (a >= 'A' && a <= 'Z') return true;
    return false;
  }
  static long long KiriageWarizan(long long a, long long b) {
    long long result = a / b;
    if (a % b > 0) result++;
    return result;
  }
  static long long GreatestCommonFactor(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    long long temp;
    if (a < b) {
      temp = b;
      b = a;
      a = temp;
    }
    while (b > 0) {
      temp = a % b;
      a = b;
      b = temp;
    }
    return a;
  }
  static long long LeastCommonMultiple(long long a, long long b) {
    return (a / GreatestCommonFactor(a, b)) * b;
  }
  static vector<vector<long long> > VVLLturn(vector<vector<long long> > a) {
    if (a.size() == 0) return vector<vector<long long> >(0);
    vector<vector<long long> > result(a[0].size(), vector<long long>(a.size()));
    long long i, j;
    for (i = 0; i < a.size(); i++) {
      for (j = 0; j < a[0].size(); j++) {
        result[j][i] = a[i][j];
      }
    }
    return result;
  }
  static vector<vector<long long> > PrimeFactorization(long long n) {
    vector<long long> p_list, s_list;
    long long i, j, k, count;
    for (i = 2; n > 1; i++) {
      if (i * i > n) {
        p_list.push_back(n);
        s_list.push_back(1);
        break;
      }
      if (n % i == 0) {
        count = 0;
        while (n % i == 0) {
          n /= i;
          count++;
        }
        p_list.push_back(i);
        s_list.push_back(count);
      }
    }
    vector<vector<long long> > result;
    result.push_back(p_list);
    result.push_back(s_list);
    return MYCP::VVLLturn(result);
  }
  static vector<long long> MakeYakusuList(long long n) {
    auto primes = MYCP::PrimeFactorization(n);
    vector<long long> ans;
    vector<long long> roop(primes.size(), 0);
    long long i, j, k, m, size = roop.size();
    while (true) {
      long long a = 1;
      for (i = 0; i < size; i++) {
        for (j = 0; j < roop[i]; j++) {
          a *= primes[i][0];
        }
      }
      ans.push_back(a);
      roop[0]++;
      for (i = 0; i < size; i++) {
        if (i + 1 < size) {
          roop[i + 1] += (roop[i] / (primes[i][1] + 1));
        }
        roop[i] %= (primes[i][1] + 1);
      }
      bool flag = true;
      for (i = 0; i < size; i++) {
        if (roop[i] != 0) flag = false;
      }
      if (flag) break;
    }
    return MYCP::Sort(ans);
  }
  static long long Combination(long long n, long long r) {
    r = min(r, n - r);
    vector<long long> p(n + 1, 0);
    long long i, j, k, a, b, c;
    for (i = 1; i <= r; i++) {
      auto temp = MYCP::PrimeFactorization(i);
      temp = MYCP::VVLLturn(temp);
      if (temp.size() == 0) {
        temp = vector<vector<long long> >(2, vector<long long>(0));
      }
      for (j = 0; j < temp[0].size(); j++) {
        p[temp[0][j]] -= temp[1][j];
      }
      a = i + n - r;
      temp = MYCP::PrimeFactorization(a);
      temp = MYCP::VVLLturn(temp);
      if (temp.size() == 0) {
        temp = vector<vector<long long> >(2, vector<long long>(0));
      }
      for (j = 0; j < temp[0].size(); j++) {
        p[temp[0][j]] += temp[1][j];
      }
    }
    long long result = 1;
    for (i = 0; i < p.size(); i++) {
      if (p[i] > 0) {
        for (j = 0; j < p[i]; j++) {
          result *= i;
          result %= MYCP::MOD_CONST;
        }
      }
    }
    return result;
  }
  static long long nHr(long long n, long long r) {
    return MYCP::Combination(n + r - 1, r);
  }
  static long long sign(long long const x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
  }
  static double PI() { return (double)3.1415926535898; }
  static void CoutDoubleKeta(double a, long long keta) {
    cout << setprecision(keta) << a << flush;
  }
  template <typename T>
  static T CoutVector(T const& ls) {
    long long i, j, k, size = distance(ls.begin(), ls.end());
    auto itr = ls.begin();
    for (i = 0; i < size - 1; i++) {
      cout << *itr << " " << flush;
      itr++;
    }
    cout << *itr << flush;
    return ls;
  }
  template <typename T>
  static T Sort(T& ls) {
    sort(ls.begin(), ls.end());
    return ls;
  }
  template <typename T, typename F>
  static T Sort(T& ls, F const& func) {
    sort(ls.begin(), ls.end(), func);
    return ls;
  }
  template <typename T>
  static T Reverse(T& ls) {
    reverse(ls.begin(), ls.end());
    return ls;
  }
  template <typename T, typename S>
  static long long Count(T const& ls, S func) {
    long long ans = 0;
    auto itr = ls.begin();
    while (itr != ls.end()) {
      if (func(*itr)) ans++;
      itr++;
    }
    return ans;
  }
  template <typename T, typename S>
  static T AllUpdate(T& ls, S func) {
    auto itr = ls.begin();
    while (itr != ls.end()) {
      *itr = func(*itr);
      itr++;
    }
    return ls;
  }
  template <typename T>
  static vector<T> FromListToVector(list<T> const& a) {
    vector<T> ans;
    for (auto itr = a.begin(); itr != a.end(); itr++) {
      ans.push_back(*itr);
    }
    return ans;
  }
  template <typename T>
  static list<T> FromVectorToList(vector<T> a) {
    list<T> ans;
    for (auto itr = a.begin(); itr != a.end(); itr++) {
      ans.push_back(*itr);
    }
    return ans;
  }
  template <typename T>
  static long long MaxElementIndex(T const& ls) {
    return distance(ls.begin(), max_element(ls.begin(), ls.end()));
  }
  template <typename T>
  static long long MinElementIndex(T const& ls) {
    return distance(ls.begin(), min_element(ls.begin(), ls.end()));
  }
  template <typename T>
  static long long DebugPrintf(T output) {
    if (MYCP::DebugFlag) {
      std::cout << output << endl;
    }
    return MYCP::DebugFlag;
  }
  static long long DebugCin() {
    long long a;
    if (MYCP::DebugFlag) {
      cin >> a;
    }
    return a;
  }
};
long long MYCP::DebugFlag = 0;
class Ruisekiwa {
 private:
  vector<long long> list;

 public:
  void MakeArray(vector<long long> data) {
    long long i;
    list = data;
    list.push_back(0);
    list[0] = 0;
    for (i = 1; i < list.size(); i++) {
      list[i] = list[i - 1] + data[i - 1];
    }
  }
  long long Sum(long long start, long long end) {
    if (end < start) {
      std::cout << "startがendより大きいです";
      return 0;
    }
    if (start < 0 || end >= list.size()) {
      std::cout << "範囲が異常";
      return 0;
    }
    return list[end] - list[start];
  }
};
class N_Number {
 public:
  N_Number(long long n, long long keta) {
    this->N_Shinsuu = n;
    vector<long long> temp(keta, 0);
    this->numbers = temp;
  }
  void plus(long long a) {
    if (a < 0) {
      a *= (-1);
      this->minus(a);
      return;
    }
    this->numbers[0] += a;
    long long size = this->numbers.size();
    for (long long i = 0; i < size; i++) {
      if (i + 1 < size) {
        this->numbers[i + 1] += this->numbers[i] / this->N_Shinsuu;
      }
      this->numbers[i] %= this->N_Shinsuu;
    }
  }
  long long check() {
    long long a = this->numbers[0];
    for (long long i = 0; i < this->numbers.size(); i++) {
      if (this->numbers[i] != a) return -1;
    }
    return a;
  }
  long long getNumber(long long keta) { return this->numbers[keta]; }
  long long getKeta() { return this->numbers.size(); }
  long long getShinsuu() { return this->N_Shinsuu; }
  void setNumber(long long keta, long long number) {
    if (0 <= number && number < this->getShinsuu()) {
      if (0 <= keta && keta < this->getKeta()) {
        this->numbers[keta] = number;
        return;
      }
    }
    cout << "er" << endl;
  }
  void setAllNumbers(long long number) {
    long long size = this->getKeta(), i;
    for (i = 0; i < size; i++) {
      this->setNumber(i, number);
    }
  }
  string to_string_KetaSoroe() {
    string s = "";
    for (long long i = this->getKeta() - 1; i >= 0; i--) {
      s += to_string(this->getNumber(i));
    }
    return s;
  }

 private:
  void minus(long long a) {
    long long i, j, k, zettaiti = abs(a);
    k = MYCP::KiriageWarizan(zettaiti, this->N_Shinsuu);
    j = k * (this->N_Shinsuu - 1);
    for (i = 0; i < this->getKeta(); i++) {
      this->numbers[i] += j;
    }
    this->numbers[0] += k - a;
    this->plus(0);
  }
  vector<long long> numbers;
  long long N_Shinsuu;
};
class Union_Find {
 private:
  vector<long long> tree;
  vector<long long> count;
  long long root(long long a) {
    if (this->tree[a] == a) return a;
    return this->tree[a] = this->root(this->tree[a]);
  }

 public:
  Union_Find(long long n) {
    vector<long long> set(n);
    this->tree = set;
    this->count = set;
    for (long long i = 0; i < n; i++) {
      this->tree[i] = i;
      this->count[i] = 1;
    }
  }
  void unite(long long a, long long b) {
    long long x, y;
    if (!this->Check(a, b)) {
      x = this->getCount(a) + getCount(b);
      y = this->root(a);
      this->count[y] = x;
      y = this->root(b);
      this->count[y] = x;
    }
    x = this->root(a);
    y = this->root(b);
    this->tree[x] = y;
  }
  bool Check(long long a, long long b) {
    return this->root(a) == this->root(b);
  }
  long long getCount(long long index) {
    long long temp = this->root(index);
    return this->count[temp];
  }
  vector<long long> getList() {
    vector<long long> ans(this->tree.size(), 0);
    for (long long i = 0; i < ans.size(); i++) {
      ans[i] = this->root(i);
    }
    return ans;
  }
};
class INF_LONG_LONG {
 private:
  long long inf, n;

 public:
  INF_LONG_LONG(long long a) {
    this->n = a;
    this->inf = 0;
    this->Syusei();
  }
  INF_LONG_LONG() { *this = INF_LONG_LONG(0); }
  INF_LONG_LONG(INF_LONG_LONG const& a) {
    this->n = a.n;
    this->inf = a.inf;
    this->Syusei();
  }
  long long getN() const { return this->n; }
  long long getInf() const { return this->inf; }
  static INF_LONG_LONG plus_inf() {
    INF_LONG_LONG a;
    a.n = 0;
    a.inf = 1;
    a.Syusei();
    return a;
  }
  static INF_LONG_LONG minus_inf() {
    INF_LONG_LONG a;
    a.n = 0;
    a.inf = -1;
    a.Syusei();
    return a;
  }
  long long sign() const {
    if (this->inf != 0) {
      return this->inf;
    }
    return MYCP::sign(this->n);
  }
  INF_LONG_LONG operator=(INF_LONG_LONG const& b) {
    this->n = b.n;
    this->inf = b.inf;
    this->Syusei();
    return *this;
  }
  INF_LONG_LONG operator=(long long const& b) {
    *this = INF_LONG_LONG(b);
    this->Syusei();
    return *this;
  }
  bool operator==(INF_LONG_LONG const& b) const {
    if (this->n == b.n && this->inf == b.inf) return true;
    return false;
  }
  bool operator!=(INF_LONG_LONG const& b) const { return !(*this == b); }
  bool operator<(INF_LONG_LONG const& b) const {
    if (this->inf < b.inf) return true;
    if (this->inf > b.inf) return false;
    return this->n < b.n;
  }
  bool operator>(INF_LONG_LONG const& b) const { return b < *this; }
  bool operator<=(INF_LONG_LONG const& b) const { return !(*this > b); }
  bool operator>=(INF_LONG_LONG const& b) const { return !(*this < b); }
  INF_LONG_LONG operator+(INF_LONG_LONG const& b) const {
    if (max(this->inf, b.inf) > 0) return INF_LONG_LONG::plus_inf();
    if (min(this->inf, b.inf) < 0) return INF_LONG_LONG::minus_inf();
    auto ans = *this;
    ans.n += b.n;
    ans.Syusei();
    return ans;
  }
  INF_LONG_LONG operator*(INF_LONG_LONG const& b) const {
    if (*this == INF_LONG_LONG(0) || b == INF_LONG_LONG(0)) {
      return INF_LONG_LONG(0);
    }
    if (this->inf != 0 || b.inf != 0) {
      long long s = this->sign() * b.sign();
      INF_LONG_LONG ans(0);
      ans.n = 0;
      ans.inf = s;
      ans.Syusei();
      return ans;
    }
    INF_LONG_LONG ans(0);
    ans.n = this->n * b.n;
    ans.Syusei();
    return ans;
  }
  INF_LONG_LONG operator-(INF_LONG_LONG const& b) const {
    auto ans = (*this + (INF_LONG_LONG(-1) * b));
    ans.Syusei();
    return ans;
  }
  INF_LONG_LONG operator/(INF_LONG_LONG const& b) const {
    if (b == INF_LONG_LONG(0)) {
      long long a = this->n / b.n;
      return INF_LONG_LONG(a);
    }
    if (b.inf != 0) {
      return INF_LONG_LONG(0);
    }
    if (*this == INF_LONG_LONG(0)) {
      return INF_LONG_LONG(0);
    }
    if (this->inf != 0) {
      long long s = this->sign() * b.sign();
      return INF_LONG_LONG::plus_inf() * INF_LONG_LONG(s);
    }
    INF_LONG_LONG ans;
    ans.n = this->n / b.n;
    ans.Syusei();
    return ans;
  }
  INF_LONG_LONG operator%(INF_LONG_LONG const& b) const {
    if (this->inf == 0 && b.inf == 0) {
      INF_LONG_LONG ans;
      ans.n = this->n % b.n;
      ans.Syusei();
      return ans;
    }
    auto x = *this / b;
    x.Syusei();
    auto ans = *this - b * x;
    ans.Syusei();
    return ans;
  }
  INF_LONG_LONG operator+=(INF_LONG_LONG const& b) {
    auto ans = *this + b;
    *this = ans;
    return *this;
  }
  INF_LONG_LONG operator-=(INF_LONG_LONG const& b) {
    auto ans = *this - b;
    *this = ans;
    return *this;
  }
  INF_LONG_LONG operator*=(INF_LONG_LONG const& b) {
    auto ans = *this * b;
    *this = ans;
    return *this;
  }
  INF_LONG_LONG operator/=(INF_LONG_LONG const& b) {
    auto ans = *this / b;
    *this = ans;
    return *this;
  }
  INF_LONG_LONG operator%=(INF_LONG_LONG const& b) {
    auto ans = *this % b;
    *this = ans;
    return *this;
  }
  INF_LONG_LONG operator+() const { return *this; }
  INF_LONG_LONG operator-() const { return *this * INF_LONG_LONG(-1); }
  INF_LONG_LONG operator++() {
    this->n++;
    this->Syusei();
    return *this;
  }
  INF_LONG_LONG operator--() {
    this->n--;
    this->Syusei();
    return *this;
  }
  INF_LONG_LONG operator++(int) {
    auto copy = *this;
    ++(*this);
    return copy;
  }
  INF_LONG_LONG operator--(int) {
    auto copy = *this;
    --(*this);
    return copy;
  }
  string ToString() const {
    if (this->inf == 1) {
      return "+INF";
    }
    if (this->inf == -1) {
      return "-INF";
    }
    return to_string(this->n);
  }

 private:
  void Syusei() {
    if (this->inf != 0) {
      this->n = 0;
    }
  }
};
class WarshallFloyd {
 public:
  vector<vector<INF_LONG_LONG> > d;
  long long v;
  WarshallFloyd(long long v, vector<vector<long long> > edge_cost_list) {
    this->v = v;
    this->d = vector<vector<INF_LONG_LONG> >(
        v, vector<INF_LONG_LONG>(v, INF_LONG_LONG::plus_inf()));
    long long i, j, k, a, b, c;
    for (i = 0; i < edge_cost_list.size(); i++) {
      a = edge_cost_list[i][0];
      b = edge_cost_list[i][1];
      c = edge_cost_list[i][2];
      this->d[a][b] = INF_LONG_LONG(c);
    }
    for (i = 0; i < v; i++) {
      this->d[i][i] = INF_LONG_LONG(0);
    }
    for (k = 0; k < v; k++) {
      for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
      }
    }
  }
};
class BellmanFord {
 public:
  vector<vector<INF_LONG_LONG> > edge;
  long long v, e;
  long long s;
  vector<INF_LONG_LONG> d;
  BellmanFord(long long v, long long start,
              vector<vector<long long> > edge_cost_list) {
    this->v = v;
    this->s = start;
    this->e = edge_cost_list.size();
    this->d = vector<INF_LONG_LONG>(v, INF_LONG_LONG::plus_inf());
    this->d[start] = 0;
    long long i, j, k;
    for (i = 0; i < this->e; i++) {
      vector<INF_LONG_LONG> temp;
      long long a, b, c;
      a = edge_cost_list[i][0];
      b = edge_cost_list[i][1];
      c = edge_cost_list[i][2];
      temp.push_back(INF_LONG_LONG(a));
      temp.push_back(INF_LONG_LONG(b));
      temp.push_back(INF_LONG_LONG(c));
      this->edge.push_back(temp);
    }
    this->DoUpdata();
    auto cpy = this->d;
    this->DoUpdata();
    for (i = 0; i < this->d.size(); i++) {
      if (this->d[i] != cpy[i]) {
        this->d[i] = INF_LONG_LONG::minus_inf();
      }
    }
    this->DoUpdata();
  }

 private:
  void DoUpdata() {
    long long i, j, k;
    for (i = 0; i <= this->v; i++) {
      bool update = true;
      for (j = 0; j < this->e; j++) {
        INF_LONG_LONG c;
        long long a, b;
        a = this->edge[j][0].getN();
        b = this->edge[j][1].getN();
        c = this->edge[j][2];
        if (this->d[a] < INF_LONG_LONG::plus_inf()) {
          if (this->d[a] + c < this->d[b]) {
            update = false;
            this->d[b] = this->d[a] + c;
          }
        }
      }
      if (update) break;
    }
  }
};
class Dijkstra {
 public:
  Dijkstra(long long v, long long start,
           vector<vector<long long> > edge_cost_list) {}
};
int main(void) {
  MYCP::DebugFlag = 0;
  long long i, j, k, n, m;
  return 0;
}
