// btree_qsort.cc : Binaerbaum + Quicksort, Version fuer de_DE.UTF-8

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <wctype.h>
#include <iostream>
#include <locale.h>
#include "quicksort.h"
using namespace std;

class Pair {
public:
  string s; int n;
  friend bool operator<(Pair& x, Pair& y) {
    if (x.n == y.n) return (strcoll( x.s.c_str(), y.s.c_str() ) < 0);
    return (x.n < y.n);
  }
  friend bool operator>(Pair& x, Pair& y) {
    if (x.n == y.n) return (strcoll( x.s.c_str(), y.s.c_str() ) > 0);
    return (x.n > y.n);
  }
};

template<class T>
class tree {
  struct node{
    T e; int c; int s; node *l, *r;
    // Element, Zaehler, Groesse, linker/rechter Teilbaum
    node() { c = s = 1; l = NULL; r = NULL; }
    friend int size (node *n)  { return ( n ? n->s : 0 );  }
  } *n;
  void consist(node *n) {
    if (n) { n->s = 1 + size(n->l) + size(n->r); }
  }

public:
  tree() { n = NULL; }        // Konstruktor : fuer Deklarationen
  tree(node *nn) { n = nn;}   // Konstruktor : fuer Initialisierungen
  friend int size(tree t) { return size(t.n); }
  node* insert(const T &e) {  // Member-Funktion :
    if (n == NULL) {
      n = new node;           // liefert und initialisiert struct node n
      n->e = e;               // Datenelement
    }
    else if (e == n->e) { n->c++; }  // e vorhanden, erhoehe Zaehler
    else if (strcoll( e.c_str(), n->e.c_str() ) < 0) // ordne lexikographisch
      n->l = tree(n->l).insert(e);
    else
      n->r = tree(n->r).insert(e);
    consist(n);
    return this->n;
  }
  friend ostream& inorder(ostream& os, tree t) {
    if (t.n) {
      inorder(os, t.n->l);
      os << t.n->e << '(' << t.n->c << ")\n" ;
      inorder(os, t.n->r);
    }
    return os;
  }
  friend Pair* inorder(Pair* p, tree t) {
    if (t.n) {
      p = inorder(p, tree(t.n->l));
      p->s = t.n->e; p->n = t.n->c; p++;
      p = inorder(p, tree(t.n->r));
    }
    return p;
  }
};

int main() {
  char s[200]; string line;
  wchar_t w[200], wline[2000], *wlp, *wp;
  tree<string> tr;                    // Deklariere Baum aus Strings
  setlocale(LC_ALL, "de_DE.UTF-8");   // cf. "man setlocale", "man locale"

  while (getline(cin,line)) {                // lies eine Zeile Text
    mbstowcs(wline,line.c_str(),2000);       // konvertiere nach wide char
    wlp = wline;
    while (*wlp) {                           // bis zum Zeilenende ...
      while (*wlp && !iswalpha(*wlp)) wlp++; // finde Wortanfang
      if (!*wlp) continue;                   // Zeile zu Ende
      wp = w;
      while (iswalpha(*wlp)) *wp++=*wlp++;   // kopiere Wort
      *wp = L'\0';                           // Wortende markieren
      wcstombs(s,w,200);                     // Wort nach UTF-8 konvertieren
      tr.insert(s);                          // in Baum einfuegen
    }
  }

  Pair *pp;
  cout << size(tr) << "\n";
  pp = new Pair[ size(tr) ];  // Anlage eines Arrays p von Pair

  cout << "Inorder arbeitet:\n";
  inorder(pp, tr);     // Ausgabe der sortierten Woerter in Array

  cout << "Quicksort arbeitet:\n";
  quicksort(pp, size(tr));

  for (int i = 0 ; i < size(tr) ; i++) {
    cout << pp[i].n << " " << pp[i].s << "\n";
  }
}